Java - Stack.pop не возвращает последний добавленный элемент

Question

В обучении программированию на Android (с использованием Android Studio) Я работаю над базовым калькулятором. Мой метод eval использует алгоритм Shain-yard Dijkstra для синтаксического анализа строкового выражения и вычисления результата. Я получил эту идею от this SO question.

Код для моего класса оценщика следующим образом:

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; 
    } 
} 

Так что мой вопрос в методе doEval. Когда я извлекаю элементы из каждого стека, я получаю первые элементы, добавленные в каждый стек. У меня создалось впечатление, что стеки были структурой First In Last Out.

Так что я могу делать неправильно? Нужно ли мне каким-то образом отменить каждый стек?

спасибо.

РЕДАКТИРОВАТЬ

Так, например, я вход 5 + 3 * 2. Я бы ожидать, что исполнение будет

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

Однако, когда я отладки это, я вижу:

pass 1: value1 = 5, Operator1 = +, value2 = 3, result = 8 
pass 2: value1 = 8 (result of pass 1), operator1 = *, value2 = 2, result = 16 

Answer 1

Ваш метод convertExpressionToStack() строит стек операнда в правильном порядке, а затем ваш метод buildOperstionStack() инвертирует его, выталкивая его и нажимая другим.

Вы действительно не нужен этот второй метод в любом случае: просто изменить метод оценки, чтобы понять x как умножение и т.д.

Answer 2

Ваше понимание стека является правильным. Это первый, последний наш или последний, первый выход.

О коде:

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); 
     } 

Поскольку вы не упомянули, как именно он ведет себя так, позвольте мне объяснить. Предположим, mOperators имеет +, - где был добавлен + первый и - на вершине +

mOperands has 3,6,2,1 

Это как ваш код будет и должен себя вести.

Для первой итерации цикла While:

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

mOperands is now: 3,6 

и после вызова mOperands.push (v), так как v теперь 1, ваш mOperands будет:

3,6,1

Вторая итерация цикла While:

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

Ваш mOperands теперь выглядит следующим образом: 3

И когда он ломает от выключателя, он будет делать mOperands как:

3,7

PS: Вы должны отладить приложение, чтобы увидеть значение mOperands на каждый шаг, чтобы получить лучшее представление о том, почему он ведет себя так, как есть.