0

In teaching myself Android programming (using Android Studio) I am working on a basic calculator app. My eval method uses Dijkstra's shunting-yard algorithm to parse a string expression and calculate the result. I got the idea for this from this SO question.

The code for my Evaluator class is as follows:

class Evaluator {
    private static Evaluator instance = new Evaluator();

    private Stack< String > mOperators;
    private Stack< Double > mOperands;

    public static Evaluator getInstance() {
        return instance;
    }

    private Evaluator() {
        mOperands = new Stack< Double >();
        mOperators = new Stack< String >();
    }

    public Double eval( String expression ) {
        Stack stack = convertExpressionToStack( expression );
        buildOperationStacks( stack );
        return doEval();
    }

    private Double doEval() {
        while ( !mOperators.isEmpty() ) {
            String op = mOperators.pop();
            Double v = mOperands.pop();

            switch ( op ) {
                case "+":
                    v = mOperands.pop() + v;
                    break;
                case "-":
                    v = mOperands.pop() - v;
                    break;
                case "*":
                    v = mOperands.pop() * v;
                    break;
                case "/":
                    v = mOperands.pop() / v;
                    break;
            }

            mOperands.push( v );
        }

        return mOperands.pop();
    }

    private void buildOperationStacks( Stack stack ) {
        while ( !stack.isEmpty() ) {
            String s = ( String ) stack.pop();

            switch ( s ) {
                case "+":
                case "-":
                case "*":
                case "x":
                case "X":
                case "/":
                case "÷":
                    if ( s.equals( "x" ) || s.equals( "X" ) ) {
                        s = "*";
                    } else if ( s.equals( "÷" ) ) {
                        s = "/";
                    }

                    mOperators.push( s );
                    break;
                default:
                    try {
                        if ( !stack.isEmpty() && stack.peek().equals  ( "." ) ) {
                            s += stack.pop();
                            s += stack.pop();
                        }

                        mOperands.push( Double.parseDouble( s ) );
                    } catch ( Exception e ) {
                        Log.e( "Error", e.getMessage() );
                    }
            }
        }
    }

    private Stack convertExpressionToStack( String expression ) {
        Stack< String > s = new Stack< String >();

        for ( char c : expression.toCharArray() ) {
            s.push( String.valueOf( c ) );
        }

        return s;
    }
}

So my issue is in the doEval method. When I pop the elements off each stack I am getting the first elements added to each stack. I was of the impression that stacks were a First In Last Out structure.

So what might I be doing wrong? Do I need to somehow reverse each stack?

Thank you.

EDIT

So for example, I input 5+3*2. I would expect the execution to be

pass 1: value1 = 2, Operator1 = *, value2 = 3 result = 6
pass 2: Value1 = 6 (result of pass 1) Operator1 = +, value2 = 5 result = 11

However, when I debug this, I am seeing:

pass 1: value1 = 5, Operator1 = +, value2 = 3, result = 8
pass 2: value1 = 8 (result of pass 1), operator1 = *, value2 = 2, result = 16
Community
  • 1
  • 1
Paul Stoner
  • 1,359
  • 21
  • 44
  • a stack is a LIFO, see http://docs.oracle.com/javase/8/docs/api/java/util/Stack.html –  Oct 07 '16 at 15:33
  • @RC. - I agree with you. First In Last Out is the same as Last In First Out. However, my stacks are acting as First In First Out. I don't understand why they are behaving this way – Paul Stoner Oct 07 '16 at 15:35
  • LIFO is not the same as FILO? But you are correct that it does not matter whether you are using lifo or filo. But it is not the same – Fjolnir Dvorak Oct 07 '16 at 15:37
  • Your understanding of stack is correct, the error lies somewhere in the logic of your code. – puhlen Oct 07 '16 at 15:42

2 Answers2

3

Your convertExpressionToStack() method is building an operand stack in the correct order, and then your buildOperstionStack() method is inverting it, by popping one and pushing the other.

You don't really need this second method anyway: just change the evaluation method to understand x as multiplication, etc.

user207421
  • 305,947
  • 44
  • 307
  • 483
0

Your understanding of Stack is correct. It's First In, Last Our or Last In, First Out.

About your code:

while ( !mOperators.isEmpty() ) {
            String op = mOperators.pop();
            Double v = mOperands.pop();

            switch ( op ) {
                case "+":
                    v = mOperands.pop() + v;
                    break;
                case "-":
                    v = mOperands.pop() - v;
                    break;
                case "*":
                    v = mOperands.pop() * v;
                    break;
                case "/":
                    v = mOperands.pop() / v;
                    break;
            }

            mOperands.push( v );
        }

Since, you have not mentioned, how exactly is it behaving, so, let me explain. Suppose, mOperators has +,- where + was added first and - on top of +

mOperands has 3,6,2,1

This is how your code will and should behave.

For the first iteration of while loop:

op = -
v = 1
v = 2-1 = 1 // since it's a -

mOperands is now: 3,6

and after call, mOperands.push(v), since v now is 1, your mOperands will be:

3,6,1

Second iteration of while loop:

op = +
v = 1
v = 6+1 = 7 // since op is +

Your mOperands now looks like: 3

And once it breaks from switch, it will make mOperands as:

3,7

P.S: You should debug your application to see values of mOperands at each and every step to get better idea, why it's behaving like it is.

SSC
  • 2,956
  • 3
  • 27
  • 43