Transcript stack

Infix and Postfix Expressions
Infix expression

Suppose the expression only has operators ‘*’
and ‘+’; and ‘*’ has a higher precedence than
‘+’.
So, 5+2+3 = 10, and 1+2*4=9, etc.
The expression may also have parenthesis to
complicate the problem, i.e.,



1.
2.
3.
(1+2)*4=12
(1+2*5+1)*3=36.
(1+2*(5+1))*3=39.
Expression Trees

An expression tree is a binary tree with the
following properties:

Each leaf is an operand.

The root and internal nodes are operators.

Subtrees are subexpressions, with the root being
an operator.
Evaluation of Postfix Expressions

Postfix expression
13+
2. 1 2 4 * +
3. 1 2 + 4 *
4. 6 5 2 3 + 8 * + 3 + *
5. 2 3 5 + 4 * 1 2 5 * + + 4 6 + * +
are all postfix expressions.
1.


No ‘(‘, ‘)’ is in the expression.
To evaluate a postfix expression, we need
a stack.
Evaluation of Postfix Expressions

Example : 6 5 2 3 + 8 * + 3 + *
Evaluation of Postfix Expressions

Evaluate a postfix expression.
1.
2.
3.
Read the expression from left-to-right.
When a number is seen, it is pushed onto the
stack.
When an operator is seen, the operator is
applied to the two numbers that are popped
from the stack. The result is pushed on the
stack.
void eval(expression e)
{
Stack <token> stack;
for(token x = NextToken(e); x != '#'; x = Nexttoken(e))
{ if (x is an operand)
stack.push(x);
else {
remove the correct number of operands for
operator x from stack; //pop the stack
perform the operation x
and push the result onto the stack;
}
}
} // Program 3.18: Evaluating postfix expressions
Infix to Postfix Expressions





a+b*c =>
(a+b)*c =>
a+b-c/d*e=>
a*(b+c-d/e)+f=>
a+b*(c*(d+e)/f)+g/h =>
Infix to Postfix Expressions

Example : (1+2*(5+1))*3
postfix expression  1 2 5 1 + * + 3 *
Infix to Postfix Expressions
How to convert an infix expression to a
postfix expression? Use a stack.

Read the infix expression from left-to-right.
1.
2.
3.
4.
5.
When an operand (number) is read, output it.
If an operator (other than ‘(‘, ‘)’) is read, pop the stack
(and output the operator) until a lower precedence
operator or ‘(‘ is on the top of stack. Then push the
current operator on the stack.
If ‘(‘ is read, push it on the stack.
If a ‘)‘ is read, pop the stacks (and output the
operators), until we meet ‘(’. Pop that ‘(’ (do no output
it).
Finally, if we read the end of the expression, pop the
stack (and output the operators) until the stack is
empty.
void Postfix(expression e)
{
stack.push(‘#’);
while (not end of expression e)
{
token=nexttoken(e);
if (token is an operand)
output token;
else if (token==‘(‘)
stack.push(token);
else if (token==‘)’)
{
while ((x=stack.pop())!=‘(‘)
output x;
}
else
{
while (precedence(x=stack.pop()) >=precedence(token))
output x;
stack.push(x);
stack.push(token);
}
}
while (not end of stack)
output stack.pop();
}