reversing data and parsing data in a stack

Expressions can be represented in prefix, postfix or infix notations and conversion from one form to another may be accomplished using a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most programming languages are context-free languages, allowing them to be parsed with stack based machines.

Evaluation of an infix expression that is fully parenthesized
Input: (((2 * 5) - (1 * 2)) / (11 - 9))
Output: 4
Analysis: Five types of input characters
Opening bracket
Numbers
Operators
Closing bracket
New line character
Data structure requirement: A character stack
Algorithm
1. Read one input character
2. Actions at end of each input
Opening brackets (2.1) Push into stack and then Go to step (1)
Number (2.2) Push into stack and then Go to step (1)
Operator (2.3) Push into stack and then Go to step (1)
Closing brackets (2.4) Pop from character stack
(2.4.1) if it is opening bracket, then discard it, Go to step (1)
(2.4.2) Pop is used four times
The first popped element is assigned to op2
The second popped element is assigned to op
The third popped element is assigned to op1
The fourth popped element is the remaining opening bracket, which can be discarded
Evaluate op1 op op2
Convert the result into character and
push into the stack
Go to step (2.4)
New line character (2.5) Pop from stack and print the answer
STOP

Evaluation of prefix expression
Input: / - * 2 5 * 1 2 - 11 9
Output: 4
Analysis: there are three types of input characters
Numbers
Operators
New line character (\n)
Data structure requirement: a character stack and an integer stack
Algorithm:
1. Read one character input at a time and keep pushing it into the character stack until the new
line character is reached
2. Perform pop from the character stack. If the stack is empty, go to step (3)
Number (2.1) Push in to the integer stack and then go to step (1)
Operator (2.2) Assign the operator to op
Pop a number from integer stack and assign it to op1
Pop another number from integer stack
and assign it to op2
Calculate op1 op op2 and push the output into the integer
stack. Go to step (2)
3. Pop the result from the integer stack and display the result
Evaluation of postfix expression
The calculation: 1 + 2 * 4 + 3 can be written down like this in postfix notation with the advantage of no precedence rules and parentheses needed:
1 2 4 * + 3 +
The expression is evaluated from the left to right using a stack:
when encountering an operand: push it
when encountering an operator: pop two operands, evaluate the result and push it.