# Evaluation of Prefix Expressions (Polish Expressions)

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.

1. Initialize a stack.
2. 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.
3. Repeat step 2 until all characters of prefix expression are scanned.

Example, let the Prefix Expression be “-*+582/62”

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 FOR``````

#### Program 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