Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Evaluation of Postfix Expression

Last Updated on June 20, 2024 by Abhishek Sharma

Evaluating postfix expressions, also known as Reverse Polish Notation (RPN), is a fundamental concept in computer science and mathematics. Unlike the more familiar infix notation, where operators are placed between operands, postfix notation places operators after their operands. This method eliminates the need for parentheses to define operator precedence, making it simpler and more efficient for computer algorithms to parse and evaluate expressions. Understanding how to evaluate postfix expressions is crucial for anyone studying data structures, algorithms, or compiler design, as it provides insights into stack operations and expression parsing.

## What is Arithmetic Expression?

An Arithmetic expression is a finite combination of arithmetic operands, operators and brackets. The common way of representing an arithmetic expression is by using infix notation. In infix notation, the operands are separated by an operator.

For example:

1. X + Y.
2. (X + Y) – Z.
3. X / Y

The infix notation is solved using the operator precedence rule.

### Operator precedence table:

Example: (4 + 5) (8 / 4 – 2) 9 (1 – 2) 9 * -1 -9

We can also represent an arithmetic expression using prefix or postfix notation.

### Whhat is Postfix Notation?

As the name suggests, post means after, hence in postfix notation the operator comes after the operators in the expression. In the postfix expression, we don’t use brackets. The prefix notation is commonly known as Reverse Polish notation.

Example: Pretfix: NM-XY+ Infix: (X + Y) (M – N)

### Algorithm to evaluate prefix notation using stack:

Below is the Algorithm to evaluate prefix notation using stack:

1. Read the expression from left to right.
2. If the current character is an operand, push it to the stack.
3. If the current character is an operator, remove the top two characters from the stack. Let’s say the removed characters are operand1 and operand2. Now. evaluate (operand1 operator operand2) and push the solution back to the stack.
4. The last character in the stack after traversing the complete prefix notation will be the solution.

### Implementation:

```
import java.util.*;
public class Prepbytes
{
public static void main(String[] args) {
char expression[] = new char[]{'2', '3', '+', '4', '5', '-', '*'};
int ans = evaluate(expression);
System.out.println(ans);
}

// This function will evaluate the given expression
public static int evaluate(char[] expression) {
Stack<Character> st = new Stack<>();

// Traverse the given expression in left to right direction
for(char ch : expression){

// If the current character is an operand, push it to the stack.
if((int)ch - '0' >= 0 && (int)ch - '0' <= 9) {
st.push(ch);
}

// If the current character is an operator.
else{

// Remove the top two characters from the stack.
int operand2 = st.pop() - '0';
int operand1 = st.pop() - '0';
int val = 0;

// Evaluate (operand1 operator operand2)
switch(ch) {
case '+':
val = operand1 + operand2;
break;
case '-':
val = operand1 - operand2;
break;
case '*':
val = operand1 * operand2;
break;
case '/':
val = operand1 / operand2;
break;
}

// Push the solution back to the stack.
st.push((char)(val + '0'));
}
}
return st.pop() - '0';
}
}

```

Output: -5

Time complexity: O(n) where n is the number of characters in the expression. Each character is pushed and popped in the stack exactly once, hence the time complexity is O(n).

Space complexity: O(n) as we are using stack.

Conclusion The evaluation of postfix expressions is a powerful technique that simplifies the parsing process by eliminating the need for parentheses and operator precedence rules. By using a stack-based approach, we can efficiently evaluate complex expressions in a straightforward manner. This method is not only essential for academic purposes but also has practical applications in areas such as compiler design, expression evaluation in calculators, and various programming languages. Mastering the evaluation of postfix expressions equips one with a deeper understanding of stack operations and enhances problem-solving skills in computer science.To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.

Below are some of the FAQs related to Evaluation of Postfix Expression:

1. What is a postfix expression? Answer: A postfix expression, also known as Reverse Polish Notation (RPN), is a mathematical notation in which every operator follows all of its operands. It differs from the more common infix notation where operators are placed between operands. For example, the infix expression "3 + 4" is written as "3 4 +" in postfix notation.

2. Why is postfix notation used? Answer: Postfix notation is used because it eliminates the need for parentheses to define operator precedence. This makes it easier for computers to parse and evaluate expressions since the order of operations is strictly left-to-right and operations are performed immediately when encountered.

3. How do you evaluate a postfix expression? Answer: To evaluate a postfix expression, you typically use a stack:

• Read the expression from left to right.
• Push operands (numbers) onto the stack.
• When an operator is encountered, pop the required number of operands from the stack, apply the operator, and push the result back onto the stack.
• The final result is found at the top of the stack after the entire expression has been processed.