consider this pseudocode:
Stack s;
while (not end of inputs) {
e = get next input;
if (e is an operand) {
s.push(e);
}
else {
op2 = s.pop();
op1 = s.pop();
value = result of operator applied on op2 and op1
s.push(value);
}
}
finalresult = s.pop();
Consider an example: 4 + 3 * 2.
The expression is in infix form.
Converting it to postfix form, we get: 4 3 2 * +.
Now apply the pseudocode on this input: 4 3 2 * +
In the beginning, the stack is empty
Since the first input
is 4
which isn't an operator
, it is pushed on the stack
.
Same for 3
and 2
.
Next input is *
operator, the operands
are poped
out of the stack
, *
operator is applied onto them and the result is pushed back into the stack
.
Next input is +
, same thing will happen.
In the end when inputs are finished,
Conversion from Infix to Postfix
We have an algorithm which changes the infix form in string, to postfix form.
Stack s;
while( not end of input ) {
c = next input character;
if( c is an operand )
add c to postfix string;
else {
while( !s.empty() && prcd(s.top(),c) ){
op = s.pop();
add op to the postfix string;
}
if (s.empty() || e != ')')
s.push( c );
else
s.pop(); //discard the '('
}
}
//cleanup in the end
while( !s.empty() ) {
op = s.pop();
add op to postfix string;
}
This algorithm is language independent.
Where prcd()
is precedence
determinant function which takes 2 arguments as inputs and returns true
if precedence of 1st
argument is higher than or equal to 2nd
one.
Additional things to consider:
prcd('(', ')'); //false
prcd(op, ')'); //true if op != '(', false if op != ')'
prcd(op, '('); //false
These are self defined such that (
forces the operands
to be pushed on the stack and when )
is encountered, the while
loop is processed.
Let us understand it using an example:
A + B * C
Since A
is an operand
, it is added to postfix
form.
Since the stack was empty, the while
loop is skipped and operator
is pushed on the stack.
Since the next input (B
) is an operand
, it is written in the postfix string.
Next input character is *
which is an operator
.
Since the stack is not empty, the while-loop condition is checked.
condition:
while (!s.empty() && prcd(s.top(), c))
Because the prcd()
function returns false
, the loop is skipped again.
The next statement is checked.
if (s.empty() || e != ')')
s.push( c );
Since *
is not )
, it is pushed.
Next input (C
) being an operand
is written in the postfix string.
Since there are not inputs left.
else
s.pop(); //discard the '('