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”

Prefix ExpressionStackDescription
-*+582/622Push 2 to Stack.
-*+582/62, 6Push 6 to Stack.
-*+582/3Pop Stack
v1 = 6
Pop Stack
v2 = 2
Push v1/v2 (3) to Stack.
-*+5823, 2Push 2 to Stack.
-*+583, 2, 8Push 8 to Stack.
-*+53, 2, 8, 5Push 5 to Stack.
-*+3, 2, 13Pop Stack
v1 = 5
Pop Stack
v2 = 8
Push v1+v2 (13) to Stack.
*3, 26Pop Stack
v1 = 13
Pop Stack
v2 = 2
Push v1*v2 (26) to Stack.
23Pop 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 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

evaluation of prefix expression 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

Leave a Comment

Your email address will not be published. Required fields are marked *