Conversion of expression in binary tree in data structure?

Answer 1

1 Mayuresh Pardeshi (pardeshimayuresh@gmail.com) /*Binary Tree Expression Solver 2 * By James Brannan, 2005. 3 * irregularexpression@gmail.com 4 * You may copy and redistribute 5 * this code free of charge as you 6 * see fit. 7 */ 8 9 using System; 10 using System.Collections.Generic; 11 using System.Text; 12 13 14 namespace Tree 15 { 16 // Node Class: Base for binary tree, holds data for left and right nodes. 17 class Node 18 { 19 // Stack used to solve for a given tree. 20private Stack stack = new Stack(); 21 22 // Solves a tree 23 public int Solve() 24 { 25 /* This method uses a stack to solve the expression. The postfix 26 * notation is tokenized and systematically added to the stack. 27 * When the stack encounters an operation, it is executed and 28 * modifies the contents on stack. The final item left on the 29 * stack (given the expression was valid) is the answer. 30 */ 31 string a , b; // Temporary placeholders for popped values 32 string[] tokens = Postfix().Split(' '); // Tokenize the postfix output 33 foreach (string e in tokens) 34 { 35 switch (e) 36 { 37 /* For operation cases, the last two items added to the stack are 38 * removed and acted upon. For any other case, the value is pushed 39 * onto the stack. 40 */ 41 case "+": 42 b = stack.Pop(); 43 a = stack.Pop(); 44 stack.Push(Convert.ToString(Convert.ToInt16(a) + Convert.ToInt16(b))); 45 break; 46 case "-": 47 b = stack.Pop(); 48 a = stack.Pop(); 49 stack.Push(Convert.ToString(Convert.ToInt16(a) - Convert.ToInt16(b))); 50 break; 51 case "/": 52 b = stack.Pop(); 53 a = stack.Pop(); 54 stack.Push(Convert.ToString(Convert.ToInt16(a) / Convert.ToInt16(b))); 55 break; 56 case "*": 57 b = stack.Pop(); 58 a = stack.Pop(); 59 stack.Push(Convert.ToString(Convert.ToInt16(a) * Convert.ToInt16(b))); 60 break; 61 case "%": 62 b = stack.Pop(); 63 a = stack.Pop(); 64 stack.Push(Convert.ToString(Convert.ToInt16(a) % Convert.ToInt16(b))); 65 break; 66 default: 67 stack.Push(e); 68 break; 69 } 70 } 71 // Value left over is the result of the expression 72 return Convert.ToInt16(stack.Pop()); 73 } 74 75 // Returns the prefix notation for the expression 76 public string Prefix() 77 { 78 /* Function recurses through the left then right 79 * nodes after its value. 80 */ 81 string res = this.Value + " "; 82 if (this.left != null) // If node is not a leaf, then recurse 83 { 84 res += this.left.Prefix(); 85 res += this.right.Prefix(); 86 } 87 return res; 88 } 89 90 // Returns the postfix notation for the expression 91 public string Postfix() 92 { 93 /*Function recurses through the left then right, 94 * bottom-up. All leafs are returned before their 95 * parent operators. 96 */ 97 string res = ""; 98 if (this.left != null) //If node is not a leaf, then recurse 99 { 100 res += this.left.Postfix() + " "; 101 res += this.right.Postfix() + " "; 102 } 103 res += this.Value; 104 return res; 105 } 106 107 // Returns the (fully parenthesized) infix notation for the expression 108 public string Infix() 109 { 110 /*Function recurses through left, then returns 111 * value, and recurses right. Each expression is 112 * nested in parentheses. 113 */ 114 string res = ""; 115 if (this.left != null) 116 { 117 res = res + "(" + left.Infix() + " " + Value + " " + right.Infix() + ")"; 118 } 119 else 120 { 121 res += Value; 122 } 123 return res; 124 } 125 126 // Constructor for subnodes 127 public Node(char op, Node l, Node r) 128 { 129 left = l; 130 right = r; 131 Value = op.ToString(); 132 } 133 // Constructor for leaf nodes 134 public Node(string value) 135 { 136 //Leaf nodes have no left or right subnodes 137 left = null; 138 right = null; 139 Value = value; 140 } 141 142 //Node connected on the left 143 private Node left; 144 // Node connected on the right 145 private Node right; 146 // Value (operator or term) 147 private string Value; 148 } 149 150 // Sample program: 151class Program 152 { 153 /* The code below demonstrates the use of the Node class. The expression being 154 * tested is graphed as shown below. (Make sure you're using a monospace font) 155 * (((1-2)-3) + (4*(5+6))) 156 * + 157 * / \ 158 * - * 159 * / \ / \ 160 * - 3 4 + 161 * / \ / \ 162 * 1 2 5 6 163 */ 164 165 static void Main(string[] args) 166 { 167 Node root = new Node('+', new Node('-', new Node('-', new Node("1"), new Node("2")), new Node("3")), 168 new Node('*', new Node("4"), new Node('+', new Node("5"), new Node("6")))); 169 Console.WriteLine("Prefix notation: \t" + root.Prefix()); 170 Console.WriteLine("Postfix notation: \t" + root.Postfix()); 171 Console.WriteLine("Infix notation: \t" + root.Infix()); 172 Console.WriteLine("Solution for tree is:\t" + root.Solve()); 173 Console.ReadKey(true); 174 } 175 } 176 }