Paul Stoner Paul Stoner - 1 month ago 10
Android Question

Java - Stack.pop does not return last item added

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

EJP EJP
Answer

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.

Comments