Stack

Reverse Polish notation

Pinterest LinkedIn Tumblr

Data structure Description

Evaluate postfix (Reverse Polish notation) is a notation in which every operator follows all of its operands. Program to evaluate postfix notation using stack and print the value.

Algorithm Explanation

Scan the Postfix string from left to right. Initialize an empty stack.
If the scanned character is an operand, add it to the stack.
If the scanned character is an operator, Pop operand from stack and store in temp1 and temp2 variable. Calculate result based on temp1 and temp2 with scanned character operator. Push to the stack
Repeat this step till all the characters are scanned.
After all characters are scanned, the stack return top Stack.

Source Code

package com.dsacode.DataStructre.stack;
 
import java.util.Stack;
 
public class EvaluatePostFix {
 
    public static Double evaluate(String postfix) {
        Stack < Double > s = new Stack < Double >();
        char[] chars = postfix.toCharArray();
 
        int N = chars.length;
 
        for (int i = 0; i < N; i++) {
            char ch = chars[i];
 
            if (isOperator(ch)) {
                switch (ch) {
                case '+':
                    s.push(s.pop() + s.pop());
                    break;
                case '*':
                    s.push(s.pop() * s.pop());
                    break;
                case '-':
                    s.push(-s.pop() + s.pop());
                    break;
                case '/':
                    s.push(1 / s.pop() * s.pop());
                    break;
                }
            } else if (Character.isDigit(ch)) {
                s.push(0.0);
                while (Character.isDigit(chars[i]))
                    s.push(10.0 * s.pop() + (chars[i++] - '0'));
            }
        }
 
        if (!s.isEmpty())
            return s.pop();
        else
            return 0.0;
    }
 
    private static boolean isOperator(char ch) {
        return ch == '*' || ch == '/' || ch == '+' || ch == '-';
    }
 
    public static void main(String[] args) {
        String postfix = "5 5 5 + *";
        System.out.println("Postfix String: " +postfix);
         
        Double value = evaluate(postfix);
        System.out.println("After eavalute postfix string: "+ value);
    }
 
}  

Output

Postfix :   234+*6-
Result :    8

Source Explanation

Get the Postfix string from the user and Create a stack to hold symbols.
Take each character from the input string. If it is a number, push to stack.
Otherwise, if it is an operator pop operands from the stack.
Based on the symbol, add, subtract, multiply or divide the numbers.
Push the result to stack finally.

Write A Comment