Data Structure

Dr. Ahmed Hesham Mostafa

Lecture 6 – Polish Notation
 Online Martials
• CS214: Data Structures by Prof. Dr Waleed A. Yousef
• https://www.youtube.com/playlist?list=PLoK2Lr1miEm-
5zCzKE8siQezj9rvQlnca
• Data Structures Learning Course by Dr Mohammed El-Said
• https://www.youtube.com/playlist?list=PLfay0LLBd0wiNeOR_SGoYfC
3w-NxFwd0D
• Lectures Source code (updated frequently)
• https://github.com/ahmedheshamostafa/DataStructure
 Polish Notation
• Polish Notation is a general form of expressing
mathematical, logical and algebraic equations. The
compiler uses this notation in order to evaluate
mathematical expressions depending on the order of
operations. There are in general three types of
Notations used while parsing Mathematical expressions:
• Infix Notation
• Prefix Notation
• Postfix Notation
 Polish Notation

Sr.No. Infix Notation Prefix Notation Postfix Notation

1 a+b +ab ab+
2 (a + b) ∗ c ∗+abc ab+c∗
3 a ∗ (b + c) ∗a+bc abc+∗
4 a/b+c/d +/ab/cd ab/cd/+
5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗
6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-
 Why ?
• We write expression in infix notation, e.g. a - b + c, where
operators are used in-between operands.
• It is easy for us humans to read, write, and speak in infix
notation but the same does not go well with computing
devices.
• An algorithm to process infix notation could be difficult and
costly in terms of time and space consumption.
 Parsing Expressions
• As we have discussed, it is not a very efficient way to design an
algorithm or program to parse infix notations. Instead, these
infix notations are first converted into either postfix or prefix
notations and then computed.
• To parse any arithmetic expression, we need to take care of
operator precedence and associativity also.
Precedence
• When an operand is in between two different operators, which
operator will take the operand first, is decided by the
precedence of an operator over others. For example −
• a + b ∗ c → a + (b ∗ c)
• As multiplication operation has precedence over addition, b * c
will be evaluated first. A table of operator precedence is
provided later.
Associativity
• Associativity describes the rule where operators with the same
precedence appear in an expression.
• For example, in expression a + b − c, both + and – have the
same precedence, then which part of the expression will be
evaluated first, is determined by associativity of those
operators.
• Here, both + and − are left associative, so the expression will
be evaluated as (a + b) − c.
 Precedence and associativity
• Precedence and associativity determines the order of evaluation of an expression.
Following is an operator precedence and associativity table (highest to lowest) −

Operator Precedence Associativity

Exponentiation ^ Highest Right Associative

Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative

Addition ( + ) & Subtraction ( − ) Lowest Left Associative

convert an Infix expression to a Postfix
expression
• o convert infix expression to postfix expression, use the stack
data structure.
• Scan the infix expression from left to right. Whenever we get
an operand, add it to the postfix expression and if we get an
operator or parenthesis add it to the stack by maintaining their
precedence.
convert an Infix expression to a Postfix
expression
Step1: Scan the infix expression from left to right.
Step2: If the scanned character is an operand, put it in the
postfix expression.
convert an Infix expression to a Postfix
expression
Step3: Otherwise, do the following
➢If the precedence and associativity of the scanned operator are greater than
the precedence and associativity of the operator in the stack [or the stack is
empty or the stack contains a ‘(‘ ], then push it in the stack. [‘^‘ operator is
right associative and other operators like ‘+‘,’–‘,’*‘ and ‘/‘ are left-associative].
➢ Check especially for a condition when the operator at the top of the stack and the
scanned operator both are ‘^‘. In this condition, the precedence of the scanned
operator is higher due to its right associativity. So it will be pushed into the operator
stack.
➢ In all the other cases when the top of the operator stack is the same as the scanned
operator, then pop the operator from the stack because of left associativity due to
which the scanned operator has less precedence.
➢Else, Pop all the operators from the stack which are greater than or equal to
in precedence than that of the scanned operator.
1. After doing that Push the scanned operator to the stack. (If you encounter
parenthesis while popping then stop there and push the scanned operator in the
stack.)
convert an Infix expression to a Postfix
expression
Step4: If the scanned character is a ‘(‘, push it to the stack.
Step5: If the scanned character is a ‘)’, pop the stack and output
it until a ‘(‘ is encountered, and discard both the parenthesis.
Step6: Repeat steps 2-5 until the infix expression is scanned.
Step7: Once the scanning is over, Pop the stack and add the
operators in the postfix expression until it is not empty.
Step8: Finally, print the postfix expression.
 Example
• Consider the infix expression exp = “a+b*c+d”
and the infix expression is scanned using the iterator i, which is initialized
as i = 0.
• 1st Step: Here i = 0 and exp[i] = ‘a’ i.e., an operand. So add this in the
postfix expression. Therefore, postfix = “a”.
• 2nd Step: Here i = 1 and exp[i] = ‘+’ i.e., an operator. Push this into the
stack. postfix = “a” and stack = {+}.
• 3rd Step: Now i = 2 and exp[i] = ‘b’ i.e., an operand. So add this in the
postfix expression. postfix = “ab” and stack = {+}.
• 4th Step: Now i = 3 and exp[i] = ‘*’ i.e., an operator. Push this into the
stack. postfix = “ab” and stack = {+, *}.
• 5th Step: Now i = 4 and exp[i] = ‘c’ i.e., an operand. Add this in the postfix
expression. postfix = “abc” and stack = {+, *}.
 Example
• 6th Step: Now i = 5 and exp[i] = ‘+’ i.e., an operator. The topmost
element of the stack has higher precedence. So pop until the stack
becomes empty or the top element has less precedence. ‘*’ is
popped and added in postfix. So postfix = “abc*” and stack = {+}.
• Now top element is ‘+‘ that also doesn’t have less precedence. Pop
it. postfix = “abc*+”. And Staxk={ }
• Now stack is empty. So push ‘+’ in the stack. stack = {+}.
• 7th Step: Now i = 6 and exp[i] = ‘d’ i.e., an operand. Add this in the
postfix expression. postfix = “abc*+d”.
• Final Step: Now no element is left. So empty the stack and add it in
the postfix expression. postfix = “abc*+d+”.
Implementation
int isDigit(char op){return op>='0'&&op<='9’;}

int isOperator(char op){return op=='+'||op=='-'||op=='*'||op=='/'||op=='^';}

int precednce(char op){

if(op=='+'||op=='-')return 1;
if(op=='/'||op=='*')return 2;
if(op=='^')return 3;
return 0;

}
void infix_to_post(char infix[],char post[]){
Stack s;
createStack(&s);
char e,t=';';
int i=0,j=0;
for(;infix[i]!='\0';i++){
e=infix[i];
if(isDigit(e)){
post[j]=e;
j++;
}
else if(e=='('){push(e,&s);}
else if(e==')'){
while(t!='('){
pop(&t,&s);
if(t!='('){
post[j]=t;
j++;
}
}
}
 else {

while(!EmptyStack(&s)&&precednce(stackTop(&s))>=precednce(e))
{
pop(&t,&s);
post[j]=t;
j++;
}
push(e,&s);

}
}//End for the for loop “end of string”
 while(!EmptyStack(&s)){
pop(&t,&s);
post[j]=t;
j++;
}
post[j]='\0';
return post;
}
 Evaluation of Postfix Expression
• Create a stack to store operands (or values).
• Scan the given expression from left to right and do the
following for every scanned element.
• If the element is a number, push it into the stack.
• If the element is an operator, pop operands for the operator from the
stack. Evaluate the operator and push the result back to the stack.
• When the expression is ended, the number in the stack is the
final answer.
 Example
• Consider the expression: exp = “2 3 1 * + 9 -“
• Scan 2, it’s a number, So push it into stack. Stack contains ‘2’.
• Scan 3, again a number, push it to stack, stack now contains ‘2
3’ (from bottom to top)
• Scan 1, again a number, push it to stack, stack now contains ‘2
3 1’
• Scan *, it’s an operator. Pop two operands from stack, apply
the * operator on operands. We get 3*1 which results in 3. We
push the result 3 to stack. The stack now becomes ‘2 3’.
 Example
• Scan +, it’s an operator. Pop two operands from stack, apply the +
operator on operands. We get 3 + 2 which results in 5. We push the
result 5 to stack. The stack now becomes ‘5’.
• Scan 9, it’s a number. So we push it to the stack. The stack now
becomes ‘5 9’.
• Scan -, it’s an operator, pop two operands from stack, apply the –
operator on operands, we get 5 – 9 which results in -4. We push
the result -4 to the stack. The stack now becomes ‘-4’.
• There are no more elements to scan, we return the top element
from the stack (which is the only element left in a stack).
• So the result becomes -4.
Implementation
float opval(char op,double val1,double val2){
if(op=='+')return val1+val2;
if(op=='-')return val1-val2;
if(op=='/')return val1/val2;
if(op=='*')return val1*val2;
if(op=='^')return pow(val1,val2);

}
float infixEval(char infix[]){
int i=0;
Stack s;
char e,val1,val2;
float res;
createStack(&s);
for(;infix[i];i++){
e=infix[i];
if(isDigit(e)){
push(e,&s);
}
else{
pop(&val2,&s) ;
pop(&val1,&s) ;
push(opval(e,(float)val1-'0',(float)val2-'0')+'0',&s);
}
}
pop(&val1,&s);
res=(float)(val1-'0');
return res;
}
int main()
{
char in[50]="",post[50]="";
printf("Enter infix String:\n ");
gets(in);
infix_to_post(in,post);
printf("The postfix for %s is =%s",in,post);
printf("\nthe eval of %s is =%f \n ",post,infixEval(post));

return 0;
}
 Infix To Prefix Algorithm
• First, reverse the order of the infix expression. For example, if the infix expression
is 4*3+(5/2), the reverse would be )2/5(+3*4.
• Next, working from left to right on the reversed infix expression, one token at a
time, determine whether or not the current token is an operand, an operator, or
an opening or closing parenthesis.
• If the token is an operand, append it to the output. Operands always appear in
the same order in the output as they do in the infix expression.
• If the token is a closing parenthesis, push it to the stack. This marks the
beginning of an expression that should be evaluated separately.
• If the token is an opening parenthesis, until a closing parenthesis is
encountered at the top of the stack, pop each operator from the stack and
append to the output. This marks the end of the operands and operators located
within the current set of parentheses.
• If the token is an operator and it has greater precedence than the operator
on the top of the stack, push the token to the stack.
 Infix To Prefix Algorithm
• If the token is an operator and it has lower precedence than the operator on the top
of the stack, until the operator on top of the stack has lower or equal precedence than
the token, or until the stack is empty, pop each operator from the stack and append them
to the output. Then push the current token to the stack.
• If the token is an operator and it has the same precedence as the operator on the
top of the stack, and the operator on top of the stack is left-to-right
associative, push the token to the stack.
• If the token is an operator and it has the same precedence as the operator on the
top of the stack, but the operator on top of the stack is right-to-left associative, until
the operator on top of the stack has lower or equal precedence than the token and is left-
to-right associative, or until the stack is empty, pop each operator from the stack and
append them to the output. Then push the current token to the stack.
• Once all of the infix tokens have been evaluated, pop any remaining operators from the
stack, one at a time, and append each of them to the output expression.
• Finally, reverse the order of the output expression to get the prefix expression.
• Example #1: A+B*C+D
• Reverse Infix Expression:
• D+C*B+A
• Scan tokens one at a time from left to right.
Character Stack Ouput
D D
Since D is an operand, print to output.
+ + D
Since + is an operator, and the stack is empty, push it to the stack.
C + DC
Since C is an operand, print to output.
* +* DC
Since * is an operator, and it has higher precedence than the + at the top of the stack, push * to the stack.
B +* DCB
Since B is an operand, print to output.
+ ++ DCB*
Since + is an operator, and it has lower precedence than the * at the top of the stack, pop * from the stack and append it to the
output, and then push + to the stack.
A ++ DCB*A
Since A is an operand, print to output.
Scanning complete.
Pop remaining 2 operators from stack, one at a time, and append to output.
+ DCB*A+
DCB*A++
Reverse final output.
Prefix: ++A*BCD
 Example
• Infix =2*(1+(4*(2+1)+3))
• First Reverse the string :
•))3+)1+2(*4(+1(*2
 Character Stack Ouput
) )
) ))
3 )) 3
+ ))+ 3
) ))+) 3
1 ))+) 31
+ ))+)+ 31
2 ))+)+ 312
( ))+ 312+
* ))+* 312+
4 ))+* 312+4
( ) 312+4*+
+ )+ 312+4*+
1 )+ 312+4*+1
( 312+4*+1+
* * 312+4*+1+
2 * 312+4*+1+2
312+4*+1+2*
Prefix: *2+1+*4+213
 References
• Evaluation of Postfix Expression – GeeksforGeeks
• Convert Infix expression to Postfix expression – GeeksforGeeks
• Postfix to Infix – GeeksforGeeks
• Data Structure - Expression Parsing (tutorialspoint.com)
• https://www.free-online-calculator-use.com/infix-to-prefix-
converter.html