第四章：如何实现一个计算器

labuladong如何实现一个计算器

227. 基本计算器 II

遇到加号，就让这个数变正
遇到减号，就让这个数变负
遇到乘号，就让当前的数乘上之前的数
遇到除号，就让当前数被之前的数除

思路：维护一个栈，若为加减，则直接入栈。若为乘除，则栈顶元素乘除当前元素，然后将栈顶弹出，将乘除后的结果入栈

方法1：stringstream提取操作子和数字（简洁易懂）

• stringstream可以根据char字符自动且智能地将字符串分隔。op为当前操作符，n为操作符后面的数字
• 在字符串前面添加+后，可使整个过程统一
• 也可以用栈代替ans来保存过程中的数字，最后对栈求和

通过while(ss>>op>>n),
+-1+10+1 会自动被提取为

+    -1
-    10
+    1

它会尽量转换并分隔字符串。即便+-1也能辨别为+和-1

// 遍历过程中，直接更新ans和n。也可以用栈保存，最后对栈求和
class Solution {
public:
    int calculate(string s) {
        stringstream ss('+'+s);
        char op;
        int n=0, ans=0, last=0;        
        while(ss>>op>>n){
            if (op=='+'|| op=='-'){
                n= (op=='+'?n:-n);
                ans+=n;
            }else{
                n=(op=='*'?last*n:last/n);
                ans=ans+n-last; // 相当于抵消掉上一个last值，把当前值代替last值
            }
            last=n;
        }
        return ans;
    }
};

方法2：逐步分解并讨论

如果是加减，则直接入栈。如果是乘除，则与栈顶元素进行计算后再入栈

• 将字符串中的空格去掉 s.erase(remove(s.begin(), s.end(), ' '), s.end());
• 如果是数字，则连续处理该数字
• 用一个sign记录（之前的）运算符。遇到某个运算符时，说明可以去讨论前面的运算了
  • 加减：直接入栈
  • 乘除：只需要把栈顶的元素弹出来，然后与当前元素相乘或相除，再将结果入栈
• 根据sign符号（加减乘除）分别进入相应的流程。先记录sign，再记录number。如3*2+3, 栈中先记录+3 -> sign符号更新为* -> 再记录2 -> 遇到+（只要遇到非数字），则处理前面的3*2并将结果6放入栈中 -> 栈中再放+3

处理空格时，如果不用erase算法，则可以：

• 遇到空格时，应该跳过。因此不要让空格进入if循环即可
  • 将if ((!isdigit(c) ) || i == s.size() - 1)改为if ((!isdigit(c) && c != ' ') || i == s.size() - 1)。即：遇到运算符则处理前面的计算
  • 处理空格时，如果要在for循环里面 if (c == ' ') continue;直接跳过。要写成if (c == ' ' && i != s.size() - 1),即:

for (int i = 0; i < s.size(); i++) {
    char c = s[i];
    if (c == ' ' && i != s.size() - 1) continue;
    ...
    }

因为类似于 3/2，空格可以直接跳过。但3/2 或3/2这种，当空格不在最后一个时，可以直接跳过。但如果最后一个也是空格，则要老老实实地进入下面的流程，否则空格后直接continue出for循环去了，2还没来得及处理。

class Solution {
public:
    stack<int> stk;

    int calculate(string s) {
        s.erase(remove(s.begin(), s.end(), ' '), s.end());
        int num = 0; // 记录单次的数字
        char sign = '+'; // 记录 num 前的符号，初始化为 +

        for (int i = 0; i < s.size(); ++i) {
            char c = s[i];
//          如果是数字，则连续处理该数字
            if (isdigit(c)) {
                num = 10 * num + (c - '0'); // 字符转int
            }
//        如果是符号或最后一个元素（要记得把最后一个元素也添加进来）
            if (!isdigit(c) || i == s.size() - 1) {
                //     注意：以下讨论的是上一个的sign符号
                if (sign == '+') {
                    stk.push(num);
                } else if (sign == '-') {
                    stk.push(-num);
                } else if (sign == '*') {
                    int tmp = stk.top() * num;
                    stk.pop();
                    stk.push(tmp);
                } else if (sign == '/') {
                    int tmp = stk.top() / num;
                    stk.pop();
                    stk.push(tmp);
                }
                // 更新符号为当前符号，数字清零
                sign = c; // 这是现在的sign符号
                num = 0;
            }
        }
        // 将栈中所有结果求和就是答案
        int res = 0;
        while (!stk.empty()) {
            res += stk.top();
            stk.pop();
        }
        return res;
    }
};

• python中，注意负数的除法取整和正数的除法取整

  我是用 python3 写的代码，这里会有个坑，坑爹的Python3「地板除 // 」。比如在 Python3 中 (-3) // 2 = -2 的（题目希望返回的是-1），和 c++ 计算负数除法的结果不一样。因此如果在计算的过程中，如果遇到负数的除法，先使用的用「浮点除 / 」再取整的方式获得和 c++一样的结果。

class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        num=0
        sign="+"
        stack=[]
        for i in range(len(s)):
            if s[i].isdigit():
                num=num*10+int(s[i])
            if s[i] in "+-*/" or i==len(s)-1:
                if sign=="+":
                    stack.append(num)
                elif sign=="-":
                    stack.append(-num)
                elif sign=="*":
                    stack.append(stack.pop()*num)
                elif sign=="/":
                    # 根据栈顶的正负数，进行区别性的除法
                    top=stack.pop() 
                    res=abs(top)//num
                    stack.append(res if top>=0 else -res)
                num=0
                sign=s[i]
        return sum(stack)

方法3：正则表达式

• 移除字符串的所有空格 s.erase(remove(s.begin(), s.end(), ' '), s.end())
• 正则表达式将字符串分解，并将分解结果放入向量v中 （如：将5+4-3*2/1 变为 5 +4 -3 *2 /1 进行计算）

注意：这里有一个非常隐蔽的bug:

• 通过re("(?=[-+*/])") 分隔字符时，若一开始就是符号，则也会提取符号前面的内容。如”-1+2”会分成””,”-1”,”+2”（注意这里有一个””）。所以迭代器要用if ((*it)=="") it++; 跳过这个空的，从下一个开始算起（因为这道题的测试用例中没有以符号开始的字符串，所以不加这句话也可以，但严格来说，应该加上）
• *it只是与空字符串””内容相同（但类型不同），所以可以用if ((*it)=="") ，不能用(*it).size() 或(*it).empty()判断是否为空

regex re("(?=[-+*/])");
sregex_token_iterator it(s.begin(), s.end(), re, -1), end;
// if ((*it)=="") it++; 注意这句话，这里不加这句话也可以通过。严格来说，应该加上
vector <string> v(it, end);

class Solution {
public:
    int calculate(string s) {
        s.erase(remove(s.begin(), s.end(), ' '), s.end()); // 去除空格
//        正则表达式：按照加减乘除将字符分开。如 1  *2  -3  +4  /5
        regex re("(?=[-+*/])");
        sregex_token_iterator it(s.begin(), s.end(), re, -1), end;
        // if ((*it)=="") it++; 注意这句话，不加这句话也可以通过。严格来说，应该加上
        vector <string> v(it, end);
//        将遍历过程的字符保存到res中，一开始先放一个元素
        vector<int> res;
        res.push_back(stoi(v[0]));        
        for (int j = 1; j < v.size(); j++) {
            string i = v[j];
            if (i[0] == '+' || i[0] == '-') {
                res.push_back(stoi(i)); // 若是加减号，则直接入栈
            } else { // 若是乘除，则计算后再入栈
                int tmp = (i[0] == '*' ? res.back() * stoi(i.substr(1)) : res.back() / stoi(i.substr(1)));
                res.pop_back();
                res.push_back(tmp);
            }
        }
        return accumulate(res.begin(), res.end(), 0);
    }
};

方法4：先分解字符串，再计算

• 要实现类似（5+4-3*2/1 变为 5 +4 -3 *2 /1）的功能，如果不想用正则表达式分解，也可以逐步遍历字符串。遇到符号时，若当前cur非空（用以规避一开头就是-的情况），则加到向量v中；其余时候字符加到cur中。

只需要把正则表达式中的

regex re("(?=[-+*/])");
sregex_token_iterator it(s.begin(), s.end(), re, -1), end;
vector <string> v(it, end);

替换为

int n=s.size();
string cur="";
vector<string> v;
for (int i = 0; i < n; ++i) {
    char c=s[i];
    if (!isdigit(c)){
        if (!cur.empty()){
            v.push_back(cur);
            cur="";
        }
    }
    cur+=c;
}
v.push_back(cur); // 添加最后一个cur

class Solution {
public:
    int calculate(string s) {
        s.erase(remove(s.begin(),s.end(),' '),s.end());

        // regex re("(?=[-+*/])");
        // sregex_token_iterator it(s.begin(), s.end(), re, -1), end;
        // vector <string> v(it, end);

        int n=s.size();
        string cur="";
        vector<string> v;
        for (int i = 0; i < n; ++i) {
            char c=s[i];
            if (!isdigit(c)){
                if (!cur.empty()){
                    v.push_back(cur);
                    cur="";
                }
            }
            cur+=c;
        }
        v.push_back(cur); // 添加最后一个cur

        vector<int> res;
        res.push_back(stoi(v[0]));
        for (int j = 1; j < v.size(); j++) {
            string i = v[j];
            if (i[0] == '+' || i[0] == '-') {
                res.push_back(stoi(i)); // 若是加减号，则直接入栈
            } else { // 若是乘除，则计算后再入栈
                int tmp = (i[0] == '*' ? res.back() * stoi(i.substr(1)) : res.back() / stoi(i.substr(1)));
                res.pop_back();
                res.push_back(tmp);
            }
        }
        return accumulate(res.begin(), res.end(), 0);
    }
};

224. 基本计算器

方法1：递归

（这里把加减乘除都考虑了）
在上一题方法2的基础上，只要遇到左括号就进入递归，遇到右括号就停止递归。不要跳进递归的过程，相信它能返回你需要的结果。（如100-（1+2）。遇到左括号时，从1开始计算。因为前面i++了。所以此时的i并不会取到( ）

• 注意if语句的顺序：得到当前的num。要先判断c是否为( ,再进入加减乘除的计算 ，再判断c是否为)。这个if语句的顺序不能变，要开始递归->计算->结束递归，否则可能会跳过某些计算。
• 左右括号一定要进入if ((!isdigit(c) && c != ' ') || i==s.size()) 语句中。因为括号也起着字段分隔的作用。遇到左括号，num要清零，遇到右括号，说明要有新的sign了（其中，sign可能会被(括号覆盖掉，但没关系，它不会影响计算结果，在下次会被新的运算符覆盖掉）
• 用一个全局变量记录当前遍历到的位置。取到当前字符时，i++

class Solution {
public:
    int i=0; // 记录string的全局下标
    int calculate(string &s) {
        stack<int> stk;
        int num = 0; // 用于把一个数字从字符转化成数字，因为一个数字可能由多个数字字符和符号组成
        char sign = '+'; // 第一个数字默认符号为'+'

        while (i<s.size()) {
            char c = s[i++];
            if (isdigit(c)){
                num = 10 * num + (c - '0'); // 字符c转成int类型
            } // 后面加括号防溢出，因为数字的ASCII值比它本身大很多

//            左括号：开始递归。注意因为前面i++了，所以这次递归不会取到左括号
            if (c == '(') num = calculate(s); // 把括号间的内容看作一个数，递归处理，这行代码要写在下面判断符号的代码前
//            处理数字。注意：左右括号一定要进入if语句。
            if ((!isdigit(c) && c != ' ') || i==s.size()) { // 不是数字和空格，那就是符号。到s末尾要结算最后一个数
                if (sign == '+') {
                    stk.push(num);
                } else if (sign == '-') {
                    stk.push(-num);
                } else if (sign == '*') {
                    int tmp = stk.top() * num;
                    stk.pop();
                    stk.push(tmp);
                } else if (sign == '/') {
                    int tmp = stk.top() / num;
                    stk.pop();
                    stk.push(tmp);
                }

                sign = c; // 更新符号位
                num = 0; // 更新计数
            }
            if (c == ')') break; // 右括号这行代码要写在上面判断符号的代码后
        }

//        计算累加和
        int res = 0;
        while (!stk.empty()) {
            res += stk.top();
            stk.pop();
        }
        return res;
    }
};

方法2：（只考虑加减）用栈模拟递归

用栈模拟递归过程。栈中Always keep most recent sum at top

• 遇到+ -，改变sign （sign取值为1 或者-1）
• 遇到（ :
  • 之前的结果入栈，之间的符号入栈
  • 更新result（用来记录括号里的累加结果）和sign（初始化sign为1）：这里相当于递归过程中重新初始化累加结果和sign
• 遇到）：
  • 用栈中之前记录的sign通过result *= stk.top()更新 result，弹出sign
  • 然后将栈中之前记录的和与现在的result合并，弹出之前的和，使栈清空

stack中始终记录最近的一次（遇到(时）的结果与sign；
result记录（遇到(后）此次括号中临时的累加和；
遇到右括号时，说明此次计算可以结束了。把临时的res与sign相乘，再与栈中之前保存的累加和相加。把所有的累加结果都更新到res中，并清空栈。

写法1：用栈模拟递归

class Solution {
public:
    int calculate(string s) {
        int n = s.size(), result = 0, sign = 1;
        stack<int> stk; // Always keep most recent sum at top
        for (int i = 0; i < n; i++) {
            if (isdigit(s[i])) {
                int num = s[i] - '0';
                while (i + 1 < n && isdigit(s[i + 1])) {
                    num = num * 10 + (s[++i] - '0');
                }
                result += sign * num;
            } else if (s[i] == '+') {
                sign = 1;
            } else if (s[i] == '-') {
                sign = -1;
            } else if (s[i] == '(') {  //这里进入括号，栈中保存历史结果，res保存括号中计算中结果，要重置，相当于递归中每层的局部变量
                stk.push(result);
                stk.push(sign);
                result = 0;
                sign = 1;
            } else if (s[i] == ')') { // Update last sum = current sum * sign 。//栈顶先是符号，然后是操作数
                result *= stk.top();
                stk.pop();
                result += stk.top();
                stk.pop();
            }
        }
        return result;
    }
};

写法2：直接写递归

用全局下标记录当前遍历位置

class Solution {
public:
    int i = 0; //全局下标方便递归中使用
    int calculate(string s) {
        if (i >= s.size()) return 0;
        int res = 0;
        char sign = '+'; //每次递归初始化
        while (i < s.size()) {
            if (s[i] == ' ') {
                i++;
                continue;
            } //遇到空格

            int cur = 0;
            if (s[i] == '(') {
                i++;
                cur = calculate(s);
            } //进括号，递归
            while (i < s.size() && '0' <= s[i] && s[i] <= '9') {
                cur = cur * 10 + int(s[i] - '0');
                i++;
            } // 处理一个数（可能有几位）

            if (sign == '+') res += cur;
            else if (sign == '-') res -= cur;

            if (s[i] == ')') {
                i++;
                return res;
            } //出括号，返回括号内结果
            else if (s[i] == '+' || s[i] == '-') sign = s[i]; //遇到操作符
            i++;
        }
        return res;
    }
};