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; Stackstack = 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