中缀后缀表达式及计算器实现

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

• 后缀表达式求值

150. 逆波兰表达式求值
     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;
    }
  };