מריה בוטוסוב

עץ בינארי שפותר ביטוי כמו מחשבון.

לדוגמה, נקח ביטוי הזה:
(((4-2)-1) + (4*(7+6)))

        	+
              /   \
             -     *
            / \   / \
            -  1 4   +
           / \      / \
          4   2    7   6


נגדיר מחלקה:

namespace Tree
{
    public class Node
    {        
        private Node left;
        private Node right;
        private string Value;
        private Stack stack = new Stack();
       
        public Node(char op, Node l, Node r)
        {
            left = l;
            right = r;
            Value = op.ToString();
        }

        public Node(string value)
        {
            // Leaf nodes have no left or right subnodes
            left = null;
            right = null;
            Value = value;
        }

        // Solves a tree
        public int Solve()
        {
           
            string a, b; // Temporary placeholders for popped values
            string[] tokens = Postfix().Split(' '); // Tokenize the postfix output
            foreach (string e in tokens)
            {
                switch (e)
                {
                    case "+":
                        b = stack.Pop();
                        a = stack.Pop();
                        stack.Push(Convert.ToString(Convert.ToInt16(a) + Convert.ToInt16(b)));
                        break;
                    case "-":
                        b = stack.Pop();
                        a = stack.Pop();
                        stack.Push(Convert.ToString(Convert.ToInt16(a) - Convert.ToInt16(b)));
                        break;
                    case "/":
                        b = stack.Pop();
                        a = stack.Pop();
                        stack.Push(Convert.ToString(Convert.ToInt16(a) / Convert.ToInt16(b)));
                        break;
                    case "*":
                        b = stack.Pop();
                        a = stack.Pop();
                        stack.Push(Convert.ToString(Convert.ToInt16(a) * Convert.ToInt16(b)));
                        break;
                    case "%":
                        b = stack.Pop();
                        a = stack.Pop();
                        stack.Push(Convert.ToString(Convert.ToInt16(a) % Convert.ToInt16(b)));
                        break;
                    default:
                        stack.Push(e);
                        break;
                }
            }
            // Value left over is the result of the expression
            return Convert.ToInt16(stack.Pop());
        }
            
        public string Postfix()
        {         
            string res = "";
            if (this.left != null) // If node is not a leaf, then recurse
            {
                res += this.left.Postfix() + " ";
                res += this.right.Postfix() + " ";
            }
            res += this.Value;
            return res;
        }
    }
}


הרצה:

static void Main(string[] args)
        {
            Node root =  new Node('+',new Node('-',new Node('-',new Node("4"),new Node("2")),new Node("1")),
                new Node('*',new Node("4"), new Node('+',new Node("7"), new Node("6")) ));

            Console.WriteLine("Solution is:\t" + root.Solve());
            Console.ReadKey(true);
        }