Stack: Evaluate Prefix Expression

Question: Evaluate a given prefix expression

Resources: https://www.youtube.com/watch?v=o6vj5l_W2h8&list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU&index=37

package additional_problems.stack;

/**
 * 1. Assume that you are given a prefix expression and that there are only single digit numbers in the expression
 * 2. Start traversing from right to left
 * 3. If operand occurred then push into stack
 * 4. If operator occurred then pop top two elements from stack and evaluate expression
 * Created by aarushi on 7/7/21.
 */
public class P04EvaluationOfPrefix {

    public static double evaluate(char operator, double operand1, double operand2){
        switch (operator){
            case '+':
                return operand1+operand2;
            case '-':
                return operand1-operand2;
            case '*':
                return operand1*operand2;
            case '/':
                return operand1/operand2;
            case '%':
                return operand1%operand2;
            case '^':
                return Math.pow(operand1, operand2);
            default:
                return 0;
        }
    }

    public static double evaluatePrefix(String prefixExpression){
        DoubleStack stack= new DoubleStack(prefixExpression.length());

        //2. Start traversing from right to left
        for (int i=prefixExpression.length()-1; i>=0; i--){
            char c= prefixExpression.charAt(i);

            //3. If operand occurred then push into stack
            if ((c >= '0' && c <= '9')) {
                stack.push((double)(c-48));
            }

            //4. If operator occurred then pop top two elements from stack and evaluate expression
            else if (c=='+' || c=='-' || c=='*' || c=='/' || c=='%' | c=='^'){
                stack.push(evaluate(c, stack.pop(), stack.pop()));
            }
        }
        
        return stack.pop();
    }

    public static void main(String [] args){
        System.out.println(evaluatePrefix("-+7*45+20"));
    }

}

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: