Post-fix tree evaluation
A fun problem from LC involving post-fix tree evaluation. Solution is actually very simple, in spite of the long problem description. Linearly scan the post-fix. If it is a number, push to the stack. Otherwise, pop, pop, evaluate, and push it back. Return the last element in the stack. That's it. Cheers! ACC
https://leetcode.com/problems/design-an-expression-tree-with-evaluate-function/
public abstract class Node
{
public abstract int evaluate();
};
public class MyNode : Node
{
private int result = 0;
private string val;
private Node left;
private Node right;
public override int evaluate()
{
return result;
}
public MyNode(string val, int result)
{
this.result = result;
this.val = val;
this.left = null;
this.right = null;
}
public MyNode(string val, int result, Node left, Node right)
{
this.result = result;
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* This is the TreeBuilder class.
* You can treat it as the driver code that takes the postinfix input
* and returns the expression tree represnting it as a Node.
*/
public class TreeBuilder
{
public Node buildTree(string[] postfix)
{
if (postfix == null || postfix.Length == 0) return null;
Stack stack = new Stack();
for (int i = 0; i < postfix.Length; i++)
{
MyNode current = null;
int number = 0;
if (Int32.TryParse(postfix[i], out number))
{
current = new MyNode(postfix[i], number);
}
else
{
int number2 = stack.Pop().evaluate();
int number1 = stack.Pop().evaluate();
int result = 0;
switch (postfix[i])
{
case "+":
result = number1 + number2;
break;
case "-":
result = number1 - number2;
break;
case "*":
result = number1 * number2;
break;
case "/":
result = number1 / number2;
break;
}
current = new MyNode(postfix[i], result);
}
stack.Push(current);
}
return stack.Pop();
}
}
Comments
Post a Comment