The Polish Notation
(Application of Stacks)
Polish Notation
Polish Notation is a way of expressing
arithmetic expressions that avoids the use
of brackets to define priorities for evaluation
of operators.
Evaluation can be achieved with great
efficiency
Operation priorities
Binary operators Unary operators
1. * / % -5
2. + – +5
3. < <= > >= + –5 = – 5
4. == != – –5 = 5
5. &&
6. ||
7. =
Polish Notation
Discovered by the polish mathematician
Jan Lukasiewicz.
Operators are either before or after their
operands:
before prefix
after postfix
Note:
between infix
Examples
ab
prefix a b
postfix a b
infix a b
Note:
a+bc Prefix and Postfix are not
mirror to each other
prefix +abc
postfix abc+
Converting Infix to Postfix with Stack
Read expression from Left-to-Right and
if an operand is read copy it to the output,
if a left parenthesis is read push it into the stack,
when a right parenthesis is encountered, the operator at the top of
the stack is popped off the stack and copied to the output until the
symbol at the top of the stack is a left parenthesis. When that occurs,
both parentheses are discarded,
if an operator is scanned and has a higher precedence than the
operator at the top of the stack, the operator being scanned is
pushed onto the stack,
while the precedence of the operator being scanned is lower than or
equal to the precedence of the operator at the top of the stack, the
operator at the top of the stack is popped and copied to the output,
when the end of the expression is reached on the input scan, the
remaining operators in the stack are popped and copied to the
output.
Example
Input: 4 * (2 – (6 * 3 + 4) * 2) + 1
Output: 4 2 6 3 * 4 + 2 * – * 1 +
* +
( ( *
– – –
( ( (
+
* * * *
Converting Infix to Prefix with Stack
Read expression from Right-to-Left and
if an operand is read copy it to the LEFT of the output,
if a right parenthesis is read push it into the stack,
when a left parenthesis is encountered, the operator at the top of the
stack is popped off the stack and copied to the LEFT of the output
until the symbol at the top of the stack is a right parenthesis. When
that occurs, both parentheses are discarded,
if an operator is scanned and has a higher or equal precedence than
the operator at the top of the stack, the operator being scanned is
pushed onto the stack,
while the precedence of the operator being scanned is lower than to
the precedence of the operator at the top of the stack, the operator at
the top of the stack is popped and copied to the LEFT of the output,
when the end of the expression is reached on the input scan, the
remaining operators in the stack are popped and copied to the LEFT of
the output.
Example
Input: 4 * (2 – (6 * 3 + 4) * 2) + 1
Output: + * 4 – 2 * + * 6 3 4 2 1
*
+
)
* * –
) ) ) *
+ + + +
Converting Infix to Prefix with Stack
2nd method
Reverse the expression
Read expression from Left-to-Right and
if an operand is read copy it to the output (left-to-right),
if a right parenthesis is read push it into the stack,
when a left parenthesis is encountered, the operator at the top of the
stack is popped off the stack and copied to the output until the
symbol at the top of the stack is a right parenthesis. When that
occurs, both parentheses are discarded,
if an operator is scanned and has a higher or equal precedence than
the operator at the top of the stack, the operator being scanned is
pushed onto the stack,
while the precedence of the operator being scanned is lower than to
the precedence of the operator at the top of the stack, the operator at
the top of the stack is popped and copied to the output,
when the end of the expression is reached on the input scan, the
remaining operators in the stack are popped and copied to the output.
Reverse the output
Example
Input: 4 * (2 – (6 * 3 + 4) * 2) + 1
Reverse: 1 + ) 2 * ) 4 + 3 * 6 ( – 2 ( * 4
Output: 1 2 4 3 6 * + * 2 – 4 * +
*
+
)
* * –
) ) ) *
+ + + +
Reverse Output: + * 4 – 2 * + * 6 3 4 2 1
Exercises
Using stack diagrams convert the following
expressions into postfix and prefix forms of
polish notation:
a) 8 – 3 4 + 2
b) 8 – 3 (4 + 2)
c) (8 – 3) (4 + 2)
d) (8 – 3) 4 + 2
e) (-a + b) (c + a) – 5
f) 2 + ((-3 + 1) (4 – 2) + 3) 6 – (1 + 2 3)
Write programs using stack for following
To convert given infix to postfix
To convert given infix to prefix
C CODE (INFIX TO POSTFIX)
#include<stdio.h>
#include<stdlib.h>
#define STACKSIZE 20
typedef struct{
int top;
char items[STACKSIZE];
}STACK;
void push(STACK *, char);
char pop(STACK *);
int preced(char);
void main()
{
int i;
char x,y, E[20] ;
STACK s;
s.top = -1;
printf("Enter the Infix Expression:");
scanf("%s",E);
for(i=0;E[i] != '\0';i++)
{
x= E[i];
if(x<=‘z’&& x>=‘a’) /* Consider all lowercase letter operands from a to z */
printf(“%c”, x);
else if(x == ‘(‘)
push(&s ,x);
else if(x == ‘)’)
{ y=pop(&s) ;
while(y != ‘(‘){
printf(“%c”,y);
y=pop(&s) ;
}
}
else
{
if(s.top ==-1 || s.items[s.top] == ‘(‘)
push(&s ,x);
else {
if (x == '/' || x == '*' || x == '+' || x == '-')
{
if (preced(x) > preced(s.items[s.top]))
push(&s ,x);
else
{
while (preced(x) <= preced(s.items[s.top]))
{
printf(“%c”, pop(&s));
}
push(&s ,x);
}
}
}}}
while(s.top != -1)
printf(“%c”,pop(&s));
}
void push(STACK *sptr, char ps) /*pushes ps into stack*/
{
if(sptr->top == STACKSIZE-1){
printf("Stack is full\n");
exit(1); /*exit from the function*/
}
else
sptr->items[++sptr->top]= ps;
}
char pop(STACK *sptr)
{
if(sptr->top == -1){
exit(1); /*exit from the function*/
}
else
return sptr->items[sptr->top--];
}
int preced(char ch)
{
if(ch == '(' || ch == ')')
return 0;
else if (ch == '+' || ch == '-')
return 1;
else if (ch== '/' || ch == '*')
return 2;
}
Evaluation of Reverse Polish
Expressions
Most compilers use the polish form to translate
expressions into machine language.
Evaluation is done using a stack data-structure
Reverse Polish Notation also called as suffix notation
Read expression from left to right and build the stack of
numbers (operands).
When an operator is read two operands are popped out
of the stack they are evaluated with the operator and the
result is pushed into the stack.
At the end of the expression there must be only one
operand into the stack (the solution) otherwise ERROR.
3 4 6 2 + 8 3 – 2 5 – 4 + + 2 6 –
62 4 + 12 8–3 5 2–5
2 3 2
6 12 8 5
4 4 16 16
3 3 3 3
5 (-3) -15 + 4 16 (-11)
-3 4
5 -15 -11
16 16 16
3 3 3
3 + (-176) 26 -173 – 12
6
-176 2 12
3 -173 -173 Result = -185
Evaluation of Polish Expressions
Evaluation is done using a stack data-structure
Polish Notation also called as prefix notation
Read expression from right to left and build the stack of
numbers (operands).
When an operator is read two operands are popped
out of the stack they are evaluated with the operator
and the result is pushed into the stack.
At the end of the expression there must be only one
operand into the stack (the solution) otherwise ERROR.
– 3 – 8 3 2 – ~ 4 – 6 2
6–2 -4 -4 – 4 32
3
6 4 -4 2
2 4 4 -8
8–6 32 6 – (-8)
8 3
6 2 6
-8 -8 -8 Result = 14
Translate each of the following expressions from
infix form into postfix and then by using stack
diagrams evaluate the postfix expressions:
a) 5 * ((-3 – 2) * (4 – 6) + 3 * 2)
b) -3 + (5 + 2) * 8 + 6 – ((4 – 2 * 3) * (-2 – 3) – 9)
c) 9 + 5 * ((3 + 2) – 8 * (1 – 3) * (-3 – 6)) + 2 * 3
d) 1 – (3 – (-1 + 2 * (6 + 7 * 2)))
