In C++ Please Specification Algorithms for expression evaluation Expression evaluation contains two major stages: Converting from infix notation to postfix notation, using a stack to store the operators (+, -, etc.) Evaluating the postfix expression, using a stack to store the operands (numbers being operated on) Infix notation is the standard expression form with which you're familiar. Operators with higher precedence (* and /) evaluate before lower-precedence operators (+ and -), with parentheses used to override that precedence. Examples of infix expressions include: 5 + 3 * 2 (4 + 2) / (3 - 1) (5 + 6 * (2 - 1)) / 4 In postfix notation, operators are written after the values, or operands, on which they operate. Operator precedence doesn't matter, so parentheses are unnecessary. Expressions are evaluated left to right. Each time you encounter an operator, it operates on the two values before it, with the operation result then replacing the numbers and operator in the expression. Here are the postfix equivalents of the infix expressions above: 5 3 2 * + 4 2 + 3 1 - / 5 6 2 1 - * + 4 / Each of the two evaluation stages can be broken down further, as described below. This link also contains an explanation of these steps, with slightly different examples. Infix to postfix conversion Parse the expression from left to right, using a stack to store the operators. As each token (piece of the input--in this case, a number, operator, or parenthesis) is encountered, do the following: If the token is a number, pass it directly to the "output" ("Output" = postfix expression. See Section 3: Hints on how to store this expression) If the token is an operator or parenthesis, change the operator stack as follows: If the token is a left parenthesis (, just push it onto the stack If the token is a right parenthesis ), check the top of the stack until you find the corresponding left parenthesis. Pop every other operator off the stack and pass each one to the output. Pop the left parenthesis but do not pass it to the output. If the token is an operator (+ - * /), check the top of the stack until you find an operator of lower priority than the current operator (or the stack is empty). Pop everything of equal or higher priority, sending each popped operator to the output. Once your program has read the entire input expression, pop every remaining operator off the stack, sending each one to the output as it's removed from the stack. Postfix expression evaluation Parse the postfix expression from left to right, using a stack to store the numbers this time. Handle each token as follows: If the token is a number, push it on the stack. If the token is an operator, pop the top two values off the stack, perform the specified operation, then push the result on the stack Once your program has parsed the entire postfix expression, the stack holds the result of evaluating the expression. Print this value, then pop it off the stack. Input specification Your program should repeatedly print the message Enter expression (or exit to end):, then read the line the user inputs. The input follows the rules below: Every valid line of input begins with a number, a left parenthesis (, or the letter e in exit Your program should print Invalid expression in all other cases. You can assume any line that starts with a number or left parenthesis is a valid expression--there are no errors in the middle of an expression. The input only contains single-digit, non-negative integers (0-9) Output specification and detailed grading rubric Your program should print the prompt described above, then print the following information in response to each type of input line (includes grading rubric that corresponds to test cases) If the user enters "exit", print Exiting program ... and end the program (5 points) If the user enters an invalid expression, print Invalid expression (10 points) For example: Enter expression (or exit to end): )1 + 2) * 3 Invalid expression If the user enters a valid expression (a line beginning with a number or ( character), print the following Print Expression:, followed by the original expression (10 points) On the next line, print Postfix form:, followed by the expression converted to postfix form (15 points) On the next line, print Result:, followed by the result of evaluating the postfix form of the expression (15 points) For example: Enter expression (or exit to end): (5 + 6 * (2 - 1)) / 4 Expression: (5 + 6 * (2 - 1)) / 4 Postfix form: 5 6 2 1 - * + 4 / Result: 2 If the user enters anything other than "exit," repeat the prompt and read another expression (5 points) For example: Enter expression (or exit to end): 5 + 3 * 2 Expression: 5 + 3 * 2 Postfix form: 5 3 2 * + Result: 11 Enter expression (or exit to end): (4 + 2) / (3 - 1) Expression: (4 + 2) / (3 - 1) Postfix form: 4 2 + 3 1 - / Result: 3 Enter expression (or exit to end): exit Exiting program ...