input expression: 3 * 12 - 4 / (5-1)

 

Operator Priorities:

(, ) == 0

+, - == 1

*, / == 2

 

algo:

 

• read from left to right
• stack initially empty
• while ( input != empty) read character
• if character == operator
• if (stack is empty)
• push operator
• else if (char priority > top of stack priority)
•  push operator
• else
• while (char priority <= top of stack priority)
• pop() and write to stdout
• push operator
• else if (char != operator)
• write to stdout
• while (stack != empty) pop() and write to stdout

 

 

Parenthesis:

• when '(' is read, push '(' unconditionally.
• when ')' is read, continually pop and print off the stack until '(' is reached.
• '(' and ')' are not printed to the screen

 

 

 

ex:        3 * 12 - 4 / (5-4 / 1)

 

Input	Output	stack
3*12-4/(5-4/1)
*12-4/(5-4/1)	3
12-4/(5-4/1)	3	*
-4/(5-4/1)	3 12	*
4/(5-4/1)	3 12 *	-
/(5-4/1)	3 12 * 4	-
(5-4/1)	3 12 * 4	-/
5-4/1)	3 12 * 4	-/(
-4/1)	3 12 * 4 5	-/(
4/1)	3 12 * 4 5	-/(-
/1)	3 12 * 4 5 4	-/(-
1)	3 12 * 4 5 4	-/(-/
)	3 12 * 4 5 4 1	-/(-/
	3 12 * 4 5 4 1 / -	-/
	3 12 * 4 5 4 1 / - / -

 

3 * 12

4 / 1

5 – 4 / 1

4 / (5-4/1)

3*12 - 4 / (5-4/1)