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

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons