Stack and Queue Applications

Balancing Symbols

A useful tool for checking your code is to see if the following symbols (), {}, and [] are properly balanced.

Every right brace, bracket, and parenthesis must have their left counterparts! The sequence [( }] is legal, and [(] is not. The simple algorithm to check the balance uses a stack:

· Make an empty stack.

· Read characters from a string.

If the character is open (, [ or { push it into the stack.
If it is a close one, pop the stack - if the popped symbol is not the corresponding opening symbol, report an error.

· If the string is empty and the stack is not, report an error.

Exercise

Implement the balancing check.

---

Infix and Postfix Notations

Typically, humans deal with expressions in infix notation where the operators (e.g. +, *) are written between the operands. Writing the operators after the operands gives postfix. In the following expression

 
2 + 5

2 and 5 are called operands, and the '+' is operator. The above arithmetic expression is called infix, since the operator is in between operands. The expression

 
2 5 +

called postfix - since the operator is after operands.

Suppose you want to compute the cost of your shopping trip. To do so, you add a list of numbers and multiply them by the local sales tax (7.25%):

70 + 150 * 1.0725

Depending on the calculator, the answer would be:

 
(70 + 150)*1.0725 = 235.95
70 + (150*1.0725) = 230.875

To avoid this confusion we shall use a postfix notation. In postfix notation the operation come after operands:

 
70 150 + 1.0725 *

Postfix has the nice property that parentheses are unnecessary.

Converting Algorithm

Here is the algorithm of converting a given infix form to a postfix form:

1. Read a given string by tokens (characters);
2. If a token is an integer you write it into the output.
3. '(' is immediately pushed on the stack.
4. You never remove '(' from the stack unless when processing ')'.
5. If a token is ')', you pop entries until you meet '('.
6. If a token is '*', '/', '+' or '-' you push it to the stack, if the stack is empty. If the stack is not empty, you pop entries with higher or equal priority and only then you push that token to the stack.
7. When you finish reading the string, you pop up all tokens which are left there.
8. Arithmetic precedence is in increasing order: '+',  '-',  '*',  '/';

Suppose we have an infix expression:

2+(4+3*2+1)/3

We read the string by characters.

'2 ' - send to the output.
'+' - push on the stack.
'(' - push on the stack.
'4' - send to the output.
'+' - push on the stack.
'3' - send to the output.
'*' - push on the stack.
'2' - send to the output.

Here is the stack after these steps:

 
| * |
| + | __________
| ( | |
| + | |2 4 3 2
|---| |__________
stack output

The next symbol is '+'. We cannot push it on the stack, see rule #6. We pop '*' and '+' from the stack and write them to the output. Then we push '+' on the stack.

 
| |
| + | __________
| ( | |
| + | |2 4 3 2 * +
|---| |__________
stack output

The next symbol is 1, which we write to the output. Then we proceed with ')'. We pop entries until we get '(', see rule #5:

 
| |
| | _______________
| | |
| + | |2 4 3 2 * + 1 +
|---| |_______________
stack output

The next symbol is '/', and then 3

 
| |
| | _______________
| / | |
| + | |2 4 3 2 * + 1 + 3
|---| |_______________
stack output

We reach the end of the string. According to rule 7, we need to pop all characters from the stack:

 
| |
| | ___________________
| | |
| | |2 4 3 2 * + 1 + 3 / +
|---| |___________________
stack output

Evaluating Postfix Expressions

Here is the algorithm of evaluating postfix forms. Consider the following postfix expression

5 9 3 + 4 2 * * 7 + *

What is the result? The easiest way to evaluate the postfix expression is to use a stack. When the number is seen, it is pushed into a stack. When the operator is seen, it is applied to two numbers popped from the stack, and then the result is pushed to the stack.

Remember, that division is not a commutative operation, so 2/3 is not the same as 3/2.

 
Stack Operations Output
--------------------------------------
push(5);  5
push(9); 5 9
push(3); 5 9 3
push(pop() + pop()) 5 12
push(4); 5 12 4
push(2); 5 12 4 2
push(pop() * pop()) 5 12 8
push(pop() * pop()) 5 96
push(7) 5 96 7
push(pop() + pop()) 5 103
push(pop() * pop()) 515