Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c
c++

How to evaluate prefix and post-fix notations

Behzad Ahmad

Let’s recall how we write a mathematical equation with basic arithmetical operations. Here is an example of a simple equation.

(((2 + 2) * 3) - 10)

This is the form that we use to write equations in normal. This notation is called infix notation. Due to the involvement of brackets, computers do not use this notation. Instead, they use either post-fix or prefix notation.

Post-fix notation

In post-fix notation, the operands come before their operators. Below is the previous equation in post-fix notation:

2 2 + 3 * 10 -

For the evaluation of post-fix notation, we use the stack data structure. The following are the rules of evaluating post-fix notation using stack:

  • Start scanning from left to right.
  • If the current value is an operand, push it onto the stack.
  • If the current is an operator, pop two elements from the stack, apply the at-hand operator on those two popped operands, and push the result onto the stack.
  • At the end, pop an element from the stack, and that is the answer.

Let’s evaluate the given example.

As the expression is empty, we simply pop an element from the stack, and that is the result of the expression.

Note: While applying the operator in the postfix evaluation, we place the second popped character at the first position, then the operator, and then the first popped element.

Prefix notation

In prefix notation, the operators come before their operands. It is also called Polish notation, or Warsaw notation. Below is the same equation in prefix notation:

- * + 2 2 3 10

For the evaluation of prefix notation, we also use the stack data structure.

The following are the rules for evaluating prefix notation using a queue:

  • Reverse the given expression.
  • Start scanning from left to right.
  • If the current value is an operand, push it onto the stack.
  • If the current is an operator, pop two elements from the stack, apply the at-hand operator on those two popped operands, and push the result onto the stack.
  • At the end, pop an element from the stack, and that is the answer.

Let’s evaluate the given example.

As the expression is empty, we simply pop an element from the stack, and that is the result of the expression.

Note: In the prefix evaluation, while applying the operator, we placed the first popped character at the first position, then the operator, and then the second popped element.

RELATED TAGS

c
c++

CONTRIBUTOR

Behzad Ahmad
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring