Reputation: 4122

Postfix Evaluation using Stacks.

I'm going insane..I'm so close to getting this code to work the way I want to I just can't figure it out. I'm trying to solve a postfix equation for ex. 3 2 + , this equals 5. When I put for example "3 2 +" in the mainmethod it works fine but as soon as I enter a 3rd digit like "3 2 + 2 *" (which equals 10) I get a arrayoutofboundserror relating back to number2 = s.pop() as you will see in the code below. Any help is greatly appreciated.

Heres the postfix meethod:

   public int PostfixEvaluate(String e){
        int number1;
        int number2;
        int result=0;

        String[] tokens = e.split(" ");

            for(int j = 0; j < tokens.length; j++){
                String token = tokens[j];
            if (!"+".equals(token) && !"*".equals(token) && !"-".equals(token) && !"/".equals(token)) {
                s.push(Integer.parseInt(token)); 

        }   else {
                String Operator = tokens[j];
                number1 = s.pop();
                number2 = s.pop();
                if (Operator.equals("/")){
                    result = number1 / number2;}
                else if(Operator.equals("*")){
                    result = number1 * number2;}
                else if(Operator.equals("+")){
                    result = number1 + number2;}
                else if(Operator.equals("-")){
                    result = number1 - number2;}
                else System.out.println("Illeagal symbol");
            }
                s.push(result);

                    s.pop();
                }


        //s.pop();
        System.out.println("Postfix Evauation = " + result);

            return result;
}

public static void main(String[] args) {
    Stacked st = new Stacked(100);
    //String y = new String("((z * j)/(b * 8) ^2");
    String x = new String("2 2 2 * +");
    TestingClass clas = new TestingClass(st);

    //clas.test(y);
     clas.PostfixEvaluate(x);

    }

}

Upvotes: 1

Answers (4)

Jeshen Appanna

Reputation: 480

The number1 assignment should be after the number2 assignment. Remember that s.pop() will remove and return the number that is on the top.

number2 = s.pop();
number1 = s.pop();

Upvotes: 3

jeantimex

Reputation: 1779

/**
 * Evaluate postfix arithmetic expression
 *
 * @example "1 12 23 + * 4 5 / -" => 34.2
 * @author  Yong Su
 */
import java.util.Stack;

class PostfixEvaluation {

    public static void main(String[] args) {
        String postfix = "1 12 23 + * 4 5 / -";
        Double value = evaluate(postfix);
        System.out.println(value);
    }

    /**
     * Evaluate postfix expression
     *
     * @param postfix The postfix expression
     */
    public static Double evaluate(String postfix) {
        // Use a stack to track all the numbers and temporary results
        Stack<Double> s = new Stack<Double>();

        // Convert expression to char array
        char[] chars = postfix.toCharArray();

        // Cache the length of expression
        int N = chars.length;

        for (int i = 0; i < N; i++) {
            char ch = chars[i];

            if (isOperator(ch)) {
                // Operator, simply pop out two numbers from stack and perfom operation
                // Notice the order of operands
                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)) {
                // Number, push to the stack
                s.push(0.0);
                while (Character.isDigit(chars[i]))
                    s.push(10.0 * s.pop() + (chars[i++] - '0'));
            }
        }

        // The final result should be located in the bottom of stack
        // Otherwise return 0.0
        if (!s.isEmpty()) 
            return s.pop();
        else
            return 0.0;
    }

    /**
     * Check if the character is an operator
     */
    private static boolean isOperator(char ch) {
        return ch == '*' || ch == '/' || ch == '+' || ch == '-';
    }
}

Upvotes: 3