逆波兰表达式应用--计算器

简介

逆波兰表达式（Reverse Polish notation） 也叫后缀表达式，可以由表达式二叉树的后序遍历得到（中序即可得到日常使用的表达式）。本文简单介绍其算法内容并实现计算器。

示例

对于表达式1+2*3+(5*6),其后缀表达式为123*+56*+

Input&Output

input：一个符合规范的表达式，如1+2*3+(5*6)，中间无空格，支持负数

output：计算结果

---

算法细节

从中缀到后缀的转换

给定一个表达式，从左到右开始读取：

• 当读到一个操作数时，将其放进postfix[]中
• 当读到一个操作符时，检查栈的状态，将元素弹出并放进postfix[]中直至栈顶为优先级更低的元素（如’*‘不低于’*‘且高于’+’)，将该操作符压入栈中，注意，’(‘不该被弹出直至读到一个’)’
• 当读到’(‘时，直接压入栈中，读到’)’时，检查栈的状态，将元素弹出并放进postfix[]中直至弹出一个’(‘，’)’不压入栈中，注意，’)’和’(‘不放入postfix[]中
• 当读取完毕时，将栈中所有元素弹入postfix[]中。

• 在这里对于负数的处理是将其看为一条”0-x”的表达式

  至此，得到了后缀表达式postfix[]。

  后缀表达式的计算（核心）

  得到后缀表达式后，继续从左到右读取：

• 遇到操作数直接压入栈中
• 遇到操作符时，弹出栈顶两个元素，并按照操作符进行运算，将结果压入栈中
• 读取完毕时，栈中仅剩一个元素，此时弹出并返回即可得到结果

---

Source Code

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>

#define MAX_SIZE 100
#define EMPTY -1
using namespace std;

class Stack {
  private:
    string sta[MAX_SIZE];
    int topEle;
  public:
    Stack() {
      topEle = EMPTY;
    }
    string pop() {
      if (topEle != EMPTY)
        return sta[topEle--];
      else
        return "";
    }
    void push(string i) {
      if (topEle != MAX_SIZE - 1)
        sta[++topEle] = i;
    }
    string top() {
      if (topEle != EMPTY)
        return sta[topEle];
    }
    bool isEmpty() {
      return topEle == EMPTY;
    }
};

int stoi(string str) {
  int num = 0, i = 0;
  if (str[0] == '-')
    ++i;
  for ( ; i < str.length(); ++i) {
    num = num * 10 + str[i] - '0';
  }
  if (str[0] == '-')
    num = -num;
  return num;
}

string getResult(string postfix[], int size) {
  Stack data;
  char num[MAX_SIZE];
  memset(num, 0, MAX_SIZE * sizeof(char));
  for (int i = 0; i < size; ++i) {
    if (postfix[i] == "+") {
      int right = stoi(data.pop());
      int left = stoi(data.pop());
      sprintf(num, "%d", left + right);
      data.push(string(num));
    } else if (postfix[i] == "-") {
      int right = stoi(data.pop());
      int left = stoi(data.pop());
      sprintf(num, "%d", left - right);
      data.push(string(num));
    }  else if (postfix[i] == "/") {
      int right = stoi(data.pop());
      int left = stoi(data.pop());
      sprintf(num, "%d", left / right);
      data.push(string(num));
    } else if (postfix[i] == "*") {
      int right = stoi(data.pop());
      int left = stoi(data.pop());
      sprintf(num, "%d", left * right);
      data.push(string(num));
    } else {
      data.push(postfix[i]);      
    }
    memset(num, 0, MAX_SIZE * sizeof(char));
  }
  return data.pop();
}

string compute(string tar) {
  string postfix[MAX_SIZE];
  Stack operation;
  string num("");
  string empty("");
  int pos(0);
  for (int i = 0; i < tar.length(); ++i) {
    if (tar[i] <= '9' && tar[i] >= '0') {
      num.push_back(tar[i]);
    } else {
      if (num != "") {
        postfix[pos++] = num;
        num = "";
      } else if (tar[i] == '-') {
        postfix[pos++] = "0";
      }
      if (tar[i] == '+' || tar[i] == '-') {
        while (!operation.isEmpty() && operation.top() != "(")
          postfix[pos++] = operation.pop();
        empty.push_back(tar[i]);
        operation.push(empty);
      } else if (tar[i] == '*' || tar[i] == '/') {
        while (!operation.isEmpty() && operation.top() != "(" && operation.top() != "+" && operation.top() != "-")
          postfix[pos++] = operation.pop();
        empty.push_back(tar[i]);
        operation.push(empty);
      } else if (tar[i] == '(') {
        empty.push_back(tar[i]);
        operation.push(empty);
      } else if (tar[i] == ')') {
        while (!operation.isEmpty() && operation.top() != "(")
          postfix[pos++] = operation.pop();
        operation.pop();
      }
      empty = "";
    }
  }
  if (num != "")
    postfix[pos++] = num;
  while (!operation.isEmpty())
    postfix[pos++] = operation.pop();
  return getResult(postfix, pos);
}

int main() {
  string tar;
  while (cin >> tar) {
    if (tar == "q")
      break;
    cout << compute(tar) << endl;
    tar = "";
  }
  return 0;
}

---

结语

这是我学栈后写的一个小程序，参考自《数据结构与算法分析——C语言描述》, Mark Allen Weiss，函数功能分工实现看上去可能比较臃肿和混乱。也没有进行表达式有效检测，主要实现算法。
感谢@chLFF 帮我指出本文的错误（陷入了“反正也没人看我为什么要改”的思考