Stack Tree

* Using Microsoft Visual C++, Write a program that takes as input a fully parenthesized arithmetic expression and converts it to a binary expression tree. Your program should display the tree in some way and also print the value associated with the root. Allow for the leaves to store variables of the form x1, x2, x3, and so on, which are initially 0 and which can be updated interactively by your program, with the corresponding update in the printed value of the root of the expression tree. * For details, please read deliverables. Comment : Try to make the program as simple as possible in the way of coding. I mean "simple" as coding the program not so complicated so that I can understand the algorithm of the program. ## Deliverables The arithmetic expression consists of: Numbers. All numbers are integer. Variables. In the format of x1, x2, x3 ...... Parentheses. They have their usual meaning. Only ( and ) will be used; don't use { } [ ]. + for addition; used only as a binary operator. - for subtraction; used only as a binary operator. * for multiplication. / for division. ===Input format=== Take the input from standard input, and the length of expression is limited to one line. For easy string tokenize of the input expression, separate the operator, operand, and parenthesis by at least one space. All variables are inputted in one line, follow the expression, with the order of x1, x2, x3 ...... For example, input expression: ( x1 + 2 ) * 4 + x2 * ( 12 - x3 / x4 ) input variables: 3 2 6 3 ===Output format=== Output the tree in the format you like. Output the prefix expression (preorder traversal of the tree). Output the final value of the expression. For the above example, output: + * + x1 2 4 * x2 - 12 / x3 x4 40 ===Expression evaluation algorithm=== You need two stacks, a operand stack (to hold the numbers and variables), and an operator stack (to hold the operators). Numbers will be int values, operators will be char values. The algorithm is roughly as follows. Note that no error checking is done explicitly. While there are still tokens to be read in, Get the next token. If the token is: A number: push it onto the operand stack. A variable: get its value, and push its value onto the operand stack. A left parenthesis: push it onto the operator stack. A right parenthesis: While the thing on top of the operator stack is not a left parenthesis, Pop the operator from the operator stack. Pop the operand stack twice, getting two operands. Apply the operator to the operands, in the correct order. Push the result onto the operand stack. Pop the left parenthesis from the operator stack, and discard it. An operator (call it thisOp): While the operator stack is not empty, and the top thing on the operator stack has the same or greater precedence as thisOp, Pop the operator from the operator stack. Pop the operand stack twice, getting two operands. Apply the operator to the operands, in the correct order. Push the result onto the operand stack. Push thisOp onto the operator stack. While the operator stack is not empty, Pop the operator from the operator stack. Pop the operand stack twice, getting two operands. Apply the operator to the operands, in the correct order. Push the result onto the operand stack. At this point the operator stack should be empty, and the operand stack should have only one value in it, which is the final result. ===Tree construction=== Create a node for each number, variable, and operator. Store the pointer to the node in the operator stack and operand stack. When applying the operator to the two operands, modify the left pointer and right pointer of the operator node, let them point to the nodes hold the two operands. ## Platform "Linux" and possibly "Microsoft Visual C++ 6.0 in Windows"