Evaluation of Prefix Expression is faster than Infix Expressions.
This is because Postfix/Prefix Expressions has no parenthesis or precedence rules.
The order in which operations are performed is defined by their order in the expression. This makes use of parenthesis and precedence rule redundant. Thus, the evaluation of expressions becomes simpler.
Infix Expressions are first converted into Prefix/Postfix Expressions. Then they are evaluated.
Evaluation of Prefix/Postfix Expressions can be performed using stack in one pass.
Algorithm
The Prefix Expression is scanned from Right-To-Left.
- Initialize a stack.
- Scan Prefix Expression from Right-To-Left.
- If the scanned character is an operand, Push it to Stack.
- If the scanned character is an operator, Pop operands from the stack depending upon the type of operator. Perform the operation and Push the result back to Stack.
- Repeat step 2 until all characters of prefix expression are scanned.
Example, let the Prefix Expression be “-*+582/62”
| Prefix Expression | Stack | Description |
|---|---|---|
| -*+582/62 | 2 | Push 2 to Stack. |
| -*+582/6 | 2, 6 | Push 6 to Stack. |
| -*+582/ | 3 | Pop Stack v1 = 6 Pop Stack v2 = 2 Push v1/v2 (3) to Stack. |
| -*+582 | 3, 2 | Push 2 to Stack. |
| -*+58 | 3, 2, 8 | Push 8 to Stack. |
| -*+5 | 3, 2, 8, 5 | Push 5 to Stack. |
| -*+ | 3, 2, 13 | Pop Stack v1 = 5 Pop Stack v2 = 8 Push v1+v2 (13) to Stack. |
| –* | 3, 26 | Pop Stack v1 = 13 Pop Stack v2 = 2 Push v1*v2 (26) to Stack. |
| – | 23 | Pop Stack v1 = 26 Pop Stack v2 = 3 Push v1-v2 (23) to Stack. |
| RESULT = 23 |
Evaluation of “-*+582/62” gives 23
Pseudo Code
prefix: Input Prefix Expression
FOR i = prefix.LENGTH-1 TO 0 DO
IF prefix[i] is operand THEN
PUSH prefix[i] TO STACK
IF prefix[i] is operator THEN
POP operands FROM THE STACK
PREFORM prefix[i] ON POPPED OPERAND
PUSH result TO STACK
END FORProgram For Evaluation of Prefix Expression
Assumptions
1. Only single-digit operands are allowed, i.e., 0 to 9.
2. Permitted Operators: +, -, /, *. All are binary operators.
#include<iostream>
#include<string>
#include<stack>
using namespace std;
bool isOperand(char c) {
return c >= '0' && c <= '9';
}
int EvaluatePrefixExpression(string prefix) {
stack<int> stk;
for (int i = prefix.length() - 1; i >= 0; --i) {
if (isOperand(prefix[i])) {
// substracting '0' convert digit in char to corresponding digit in int
stk.push(prefix[i] - '0');
}
else {
// we are assuming that expression only contain binary operations
// in case expression contains multiple types of operators
// then number of operands depend on the type of operator
// for unary 1 operand is popped, for binary 2, for ternary 3 and so on
int v1 = stk.top();
stk.pop();
int v2 = stk.top();
stk.pop();
switch (prefix[i]) {
case '*':
stk.push(v1 * v2);
break;
case '/':
stk.push(v1 / v2);
break;
case '+':
stk.push(v1 + v2);
break;
case '-':
stk.push(v1 - v2);
break;
}
}
}
return stk.top();
}
int main() {
string prefix;
cout << "Enter Prefix Expression: ";
cin >> prefix;
int result = EvaluatePrefixExpression(prefix);
cout << "Result of Evaluation: " << result << endl;
}
Output
Note
In the above Program, we pop 2 operators without check the type of operator. This is because we have included only Binary Operators.
If the program contains multiple types of operators, i.e., unary, ternary, etc. Then we must check the operator type before popping operands.
Complexity
Time Complexity: O(N)
Space Complexity: O(N)
References
https://en.wikipedia.org/wiki/Polish_notation