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.

- If the
- 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 Stackv1 = 6Pop Stack v2 = 2Push 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 Stackv1 = 5Pop Stack v2 = 8Push v1+v2 (13) to Stack. |

–* | 3, 26 | Pop Stackv1 = 13Pop Stack v2 = 2Push v1*v2 (26) to Stack. |

– | 23 | Pop Stackv1 = 26Pop Stack v2 = 3Push 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 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