Калькулятор C++ с использованием стеков и очередей

Я пытаюсь понять тему в классе об использовании стеков и очередей в качестве средства программирования калькулятора. Я понимаю, что такое инфиксное и постфиксное выражение, но как облегчить программе вычисление выражения и почему очереди и стеки идеальны в этой ситуации? Спасибо


c++ stack queue calculator postfix-notation
person Richard    schedule 04.03.2012    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Это упрощает обработку порядка операций, например:

+ * - 4 2 5 3

Может означать только

((4 - 2) * 5) + 3

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

Что касается реализации: если бы у вас был стек, вы могли бы обработать приведенное выше выражение следующим образом:

  1. Прочитайте + (операция), поместите его в стек,
  2. Прочитайте * (операция), поместите его в стек,
  3. Прочитайте - (операция), поместите его в стек,
  4. Прочитайте 4 (число), вершина стека не является числом, поэтому поместите его в стек.
  5. Прочитайте 2 (число), вершина стека — это число, поэтому извлеките из стека дважды, вы получите 4 - 2, вычислите его (2) и поместите результат (2) в стек.
  6. Прочитайте 5 (число), вершина стека - это число, поэтому дважды извлеките из стека, вы получите 2 * 5, поместите результат (10) в стек.
  7. Прочитайте 3 (число), вершина стека - это число, поэтому дважды извлеките из стека, вы получите 3 + 10, поместите результат (13) в стек.
  8. Читать нечего, вытаскиваем из стека и возвращаем результат (13).

Итак, как вы можете видеть, выражение вычислялось с использованием нескольких простых правил и без необходимости поиска во всей строке скобок или необходимости решать, имеет ли умножение приоритет над сложением и вычитанием.

person trutheality    schedule 04.03.2012