Consider the following input and output:
INPUT: (((5 + 1) – (7 – 4)) / (11 – 8))
OUTPUT: 5 1 + 7 4 – – 11 8 - /
2.1. What variables do you need to consider for the input?
2.2. Describe in English, step by step, the algorithm that transforms the given input into the given output. [Hint: You need to use a stack].
2.3. Trace your algorithm by hand with the given input. Your trace MUST show the current character to be read, the operation to be applied, the content of the stack, and the output printed on the screen.
2.4. Can you determine the conversion that has been applied on the given input?
2.1. The variables you need to consider for the input are the mathematical expressions and operators. In this case, the input consists of parentheses, numbers, and arithmetic operators such as addition, subtraction, and division.
2.2. To transform the given input into the given output, you can use the following algorithm:
1. Initialize an empty stack and an empty output string.
2. Read each character from left to right in the input.
3. If the character is an operand (a number), add it to the output string.
4. If the character is an opening parenthesis, push it onto the stack.
5. If the character is an operator, check the precedence of the operator.
a. If the stack is empty or the top of the stack is an opening parenthesis, push the operator onto the stack.
b. If the precedence of the operator is higher than the precedence of the top of the stack, push the operator onto the stack.
c. If the precedence of the operator is lower than or equal to the precedence of the top of the stack, pop the operators from the stack and add them to the output string until a lower-precedence operator is encountered or the stack becomes empty. Then push the current operator onto the stack.
6. If the character is a closing parenthesis, pop the operators from the stack and add them to the output string until an opening parenthesis is encountered. Discard the opening parenthesis.
7. Repeat steps 3-6 until all characters have been processed.
8. Pop any remaining operators from the stack and add them to the output string.
9. The output string is the desired output.
2.3. Here is a trace of the algorithm with the given input:
Input: (((5 + 1) – (7 – 4)) / (11 – 8))
Character Operation Stack Output
------------------------------------------------
( Push ( -
( Push ( ( -
( Push ( ( ( -
5 Append ( ( ( 5
+ Push ( ( ( + 5
1 Append ( ( ( + 5 1
) Pop and Append ( ( 5 1 +
- Push ( ( - 5 1 +
( Push ( ( - ( 5 1 +
7 Append ( ( - ( 5 1 + 7
- Push ( ( - ( - 5 1 + 7
4 Append ( ( - ( - 5 1 + 7 4
) Pop and Append ( 5 1 + 7 4 -
) Pop and Append 5 1 + 7 4 - -
/ Push / 5 1 + 7 4 - -
( Push / ( 5 1 + 7 4 - -
11 Append / ( 5 1 + 7 4 - - 11
- Push / ( - 5 1 + 7 4 - - 11
8 Append / ( - 5 1 + 7 4 - - 11 8
) Pop and Append / 5 1 + 7 4 - - 11 8 -
5 1 + 7 4 - - 11 8 - /
2.4. The conversion applied to the given input is called the Reverse Polish Notation (RPN) or Postfix Notation. In this notation, the operators are placed after their operands. The algorithm converts the input expression to this notation, where each number and operator is separated by a space.