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.

Dry run to evaluate prefix notation using stack:

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.

Frequently Asked Questions (FAQs) about Evaluation of Postfix Expression

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.

4. What are the advantages of using postfix notation? Answer: Advantages include:

• Simplified Parsing: No need for parentheses and operator precedence rules.
• Efficient Evaluation: Stack-based evaluation is straightforward and efficient.
• Ease of Implementation: Postfix expressions are easier to evaluate programmatically, making them useful in compilers and calculators.

5. Can you convert an infix expression to a postfix expression? Answer: Yes, an infix expression can be converted to a postfix expression using the Shunting Yard algorithm, developed by Edsger Dijkstra. This algorithm uses a stack to hold operators and ensures that operators are output in the correct order according to their precedence and associativity.

6. What is the role of the stack in postfix evaluation? Answer: The stack plays a crucial role in postfix evaluation. It is used to store operands and intermediate results during the evaluation process. Operators then use these operands from the stack, perform the required operations, and push the results back onto the stack.