Algorithm to evaluate a prefix expression

Algorithm

Suppose P is an expression written in prefix notation. This algorithm finds VALUE of prefix expression P.

1) Add ‘(’ in the beginning of P.
2) Scan P from right to left and repeat step3 and step4 for each symbol of P until sentinel ‘(’ is encountered.
3) If an operand is encountered, push it onto stack
4) If an operator  is encountered, then
a) Pop two elements from the stack, where A is topmost element and B is next to top element.
b) Evaluate AB.
c) Push above result onto stack.
5) VALUE ← top element on the stack.
6) Exit.

Algorithm to evaluate a postfix expression

Algorithm

Suppose P is an expression written in postfix notation. This algorithm finds VALUE of postfix expression P.

1) Add ‘)’ to the end of P.
2) Scan P from left to right and repeat step3 and step4 for each symbol of P until sentinel ‘)’ is encountered.
3) If an operand is encountered, push it onto stack
4) If an operator  encountered, then
a) Pop two elements from the stack, where A is topmost element and B is next to top element.
b) Evaluate BA.
c) Push above result onto stack.
5) VALUE ←top element on the stack.
6) Exit.

Algorithm for converting infix expression to prefix expression

Algorithm

PREFIX (Q, P)

Suppose Q is an expression written in infix notation. This algorithm finds equivalent prefix expression P.
1) Reverse the infix expression Q with exchanging left and right parenthesis and store into Q.
2) Convert Q into postfix P using algorithm1.
3) Reverse the expression P and get prefix expression.
4) Exit.

Algorithm for converting infix expression to postfix expression

Algorithm

POSTFIX (Q, P)

Suppose Q is an expression written in infix notation. This algorithm finds equivalent postfix expression P.

1) Push ‘(‘onto stack, and add ‘)’ to the end of Q.
2) Scan Q from left to right and repeat step3 to step6 for each symbol of Q until the stack is empty.
3) If an operand is encountered, add it to P.
4) If an left parenthesis is encountered, push it onto stack
5) If an operator  encountered, then
a) Repeatedly pop from stack and add to P each operator (on the top of stack) which has same or higher precedence than.
b) Push  onto stack.
6) If an right parenthesis encountered, then
a) Repeatedly pop from stack and add to P each operator (on the top of stack) until left parenthesis is encountered.
b) Remove left parenthesis from stack.
[Do not add left parenthesis to P]
7) Exit.

Algorithm for converting infix expression to prefix expression

Algorithm

PREFIX (Q, P)

Suppose Q is an expression written in infix notation. This algorithm finds equivalent prefix expression P.
1) Reverse the infix expression Q with exchanging left and right parenthesis and store into Q.
2) Convert Q into postfix P using algorithm1.
3) Reverse the expression P and get prefix expression.
4) Exit.

Algorithm for converting infix expression to postfix expression

Algorithm

POSTFIX (Q, P)

Suppose Q is an expression written in infix notation. This algorithm finds equivalent postfix expression P.

1) Push ‘(‘onto stack, and add ‘)’ to the end of Q.
2) Scan Q from left to right and repeat step3 to step6 for each symbol of Q until the stack is empty.
3) If an operand is encountered, add it to P.
4) If an left parenthesis is encountered, push it onto stack
5) If an operator  encountered, then
a) Repeatedly pop from stack and add to P each operator (on the top of stack) which has same or higher precedence than.
b) Push  onto stack.
6) If an right parenthesis encountered, then
a) Repeatedly pop from stack and add to P each operator (on the top of stack) until left parenthesis is encountered.
b) Remove left parenthesis from stack.
[Do not add left parenthesis to P]
7) Exit.

Algorithm to evaluate a prefix expression

Algorithm

Suppose P is an expression written in prefix notation. This algorithm finds VALUE of prefix expression P.

1) Add ‘(’ in the beginning of P.
2) Scan P from right to left and repeat step3 and step4 for each symbol of P until sentinel ‘(’ is encountered.

3) If an operand is encountered, push it onto stack
4) If an operator  is encountered, then
a) Pop two elements from the stack, where A is topmost element and B is next to top element.

b) Evaluate AB.
c) Push above result onto stack.
5) VALUE ← top element on the stack.
Exit.