Algorithm to evaluate a prefix expression

A prefix expression is a mathematical expression in which the operator comes before the operands. For example, + 5 3 means 5 + 3. Evaluating a prefix expression means calculating its result step by step.

The algorithm works by reading the expression from right to left (opposite to how we normally read). Whenever we see a number (operand), we push it onto a stack. When we see an operator like +, -, *, or /, we pop the required numbers from the stack, perform the operation, and push the result back onto the stack. At the end, the stack will contain the final answer.

This method is simple, fast, and avoids confusion with parentheses, making it very useful in computers and calculators

What is Prefix expression ?

A prefix expression is a way of writing mathematical expressions where the operator comes before the operands. For example, instead of writing A + B (infix form), we write it as + A B in prefix form.

Prefix expressions are easy for computers to evaluate because they don’t need brackets or operator precedence rules — the order of operations is clear from the position of the operator. For example, the infix expression A + B * C becomes + A * B C in prefix form, which means multiply B and C first, then add A to the result.

Point to consider

1. Permitted operands: A,B,C,D means any real number is permitted.
2. Permitted operators: +,-, *, /, ^(exponentiation)
3. Blanks are permitted in the expression
4. Parenthesis are permitted

Prefix and Postfix expressions can be evaluated faster in comparison to an infix expression because we don’t need to process any brackets or follow operator precedence rule. In postfix and prefix expressions which ever operator comes before will be evaluated first, irrespective of its priority. Also, there are no brackets in these expressions. As long as we can guarantee that a valid prefix or postfix expression is used, it can be evaluated with correctness.

Algorithm to evaluate prefix expression

Step 1: Start Evaluating expression from right to left or reverse the expression
Step 2: If a character is an operand push it to Stack
Step 3: If the character is an operator
pop two elements from the Stack.
Operate on these elements according to the operator, and push the result back to the Stack
Step 4: Step 2 and 3 will be repeated until the end has reached.
Step 5: The Result is stored at the top of the Stack, return it
Step 6: End

Example of prefix expression

Expression: - * + 2 3 4 5

We need to evaluate this step by step.

Step 1: Understand the Expression

• Prefix means operator comes first, then operands.
• The expression can be read as:

- ( * ( + 2 3 ) 4 ) 5

In normal infix notation, it becomes:

((2 + 3) * 4) - 5

Step 2: Use a Stack to Evaluate (Right to Left)

We read from right to left: 5, 4, 3, 2, +, *, -.

1. Push operands onto the stack.
   • Stack: 5
   • Next, push 4 → Stack: 5, 4
   • Next, push 3 → Stack: 5, 4, 3
   • Next, push 2 → Stack: 5, 4, 3, 2
2. Encounter an operator +:
   • Pop two operands from stack: 2 and 3
   • Perform operation: 2 + 3 = 5
   • Push result back → Stack: 5, 4, 5
3. Next operator *:
   • Pop two operands: 5 and 4
   • Multiply: 5 * 4 = 20
   • Push result → Stack: 5, 20
4. Next operator -:
   • Pop two operands: 20 and 5
   • Subtract: 20 - 5 = 15
   • Push result → Stack: 15

Step 3: Final Result

• Only one value remains in the stack: 15
• So, the result of - * + 2 3 4 5 is 15

Complexity of Prefix evaluation

The Prefix evaluation algorithm has linear complexity O(N). Since we scan the expression once and perform push and pop operations which take constant time.

Conclusion

Evaluating a prefix expression using a stack is simple, fast, and efficient. By reading the expression from right to left, pushing operands onto the stack, and applying operators to the top elements, we can calculate the result without worrying about parentheses or operator precedence. This method is widely used in computers, calculators, and compilers because it ensures accurate and quick evaluation of mathematical expressions.