实现中缀后缀表达式以及基本的计算器功能

  • 后缀表达式求值
  1. 逆波兰表达式求值
    https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

    // 隐藏BUG,如果要用stoi或者atoi函数,必须要是有效数字才可以判断,否则输入“+”这种符号,会抛出异常
    int evalRPN(vector<string>& tokens) {
    // int res;
    stack<int> st;
    //    for (auto& token : tokens) {
    for (int i = 0; i < tokens.size(); i++) {
    //        if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
    //            int num1 = st.top();
    //        st.pop();
    //        int num2 = st.top();
    //        st.pop();
    //        if (tokens[i] == "+") st.push(num2 + num1);
    //        if (tokens[i] == "-") st.push(num2 - num1);
    //        if (tokens[i] == "*") st.push(num2 * num1);
    //        if (tokens[i] == "/") st.push(num2 / num1);
    //        } else {
    //            st.push(stoi(tokens[i]));
    //        }
    //    }
    
       int temp1, temp2;
       string& token = tokens[i];
       if (tokens[i] == "+") {
           temp1 = st.top();
           st.pop();
           temp2 = st.top();
           st.pop();
           st.push(temp1 + temp2);
       } else if (tokens[i] == "-") {
           temp1 = st.top();
           st.pop();
           temp2 = st.top();
           st.pop();
           st.push(temp2 - temp1);
       } else if (tokens[i] == "*") {
           temp1 = st.top();
           st.pop();
           temp2 = st.top();
           st.pop();
           st.push(temp2 * temp1);
       } else if (tokens[i] == "/") {
           temp1 = st.top();
           st.pop();
           temp2 = st.top();
           st.pop();
           st.push(temp2 / temp1);
       } else {
           st.push(std::stoi(tokens[i]));
       }
    }
    return st.top();
    }
  • 中缀表达式基础版
    基本思想是将乘除的结果压入栈中,加减的话,直接带上符号压入栈中,最后计算所有加减的结果
    面试题 16.26. 计算器
    https://leetcode-cn.com/problems/calculator-lcci/
    class Solution {
    public:
      int calculate(string s)
      {
          char preSign = '+';
          stack<int> st;
          for (int i = 0; i < s.size(); i++) {
              if (s[i] == ' ') {
                  continue;
              }
              if (s[i] >= '0' && s[i] <= '9') {
                  int num = 0;
                  // while 的 意义
                  while (i < s.size() && s[i] >= '0' && s[i] <= '9') {
                      num = num * 10 + (s[i] - '0'); // s[i] - '0'的计算需要加括号
                      i++;
                  }
                  i--;
                  if (preSign == '*') {
                      int temp = st.top();
                      st.pop();
                      st.push(num * temp);
                  }
                  if (preSign == '/') {
                      int temp = st.top();
                      st.pop();
                      st.push(temp / num);
                  }
                  if (preSign == '+') {
                      st.push(num);
                  }
                  if (preSign == '-') {
                      st.push(-num);
                  }
              } else {
                  preSign = s[i];
              }
          }
          int res = 0;
      //    for (int i = 0; i < st.size(); i++) {
      //        res += st.top();
      //        st.pop(); // 隐藏的BUG,醉了,pop之后会导致边界core dump
      //    }
          while (!st.empty()) {
              res += st.top();
              st.pop();
          }
          return res;
      }
    };