0

计算器问题

 2 years ago
source link: https://yuanjie-ai.github.io/2022/04/13/calculator/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

计算器问题

发表于

2022-04-13

阅读次数： 4 本文字数： 2.3k 阅读时长 ≈ 2 分钟

计算器问题大约在大二数据结构的课程上学过，当时是使用栈来解决，此外还需要设置很多符号的优先级，以此判断是否弹栈，代码写的很长很麻烦。今天又遇到了这种题，也有了简单的解法，做一个整理。

计算器的难点在于先算乘除后算加减，如果有小括号，需要先算括号里面的内容。因此从简往难，一点点的来看问题如何解决。

无括号相对简单一些，我们只需要考虑先算乘除后算加减即可。那么思路就是：如果当前符号是加法或减法，那么将符号连带数字压入栈中，比如 +10 或 -11；如果遇到的是乘法或除法，那么就需要把栈尾的元素拿出来，做乘法或除法运算在放入栈中。最后，对栈内的元素求和即可。

我们来看程序：

class Solution {
public:
    int calculate(string s) {
        int idx = 0;
        return subcal(s, idx);
    }
    int subcal(string s, int& idx) {
        int res = 0;
        stack<int> stk;
        int num = 0;
        char sign = '+';
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (isdigit(c)) {
                num = 10 * num + (c - '0');
            } 
            if (!isdigit(c) && c != ' ' || i == s.size() - 1) {
                if (sign == '+') {
                    stk.push(num);
                } else if (sign == '-') {
                    stk.push(-num);
                } else if (sign == '*') {
                    auto tmp = stk.top();
                    stk.pop();
                    stk.push(tmp * num);
                } else if (sign == '/') {
                    auto tmp = stk.top();
                    stk.pop();
                    stk.push(tmp / num);
                }
                sign = c;
                num = 0;
            }
        }
        while (stk.size()) {
            res += stk.top();
            stk.pop();
        }
        return res;
    }
};

程序中有很多的细节，一点点来分析：

  • sign 初始值为 +，这样如果开头的数字是正数，那么这个数会被放入栈中；如果开头的数字是负数，那么栈中先放入 0，在放入负数，不影响。
  • 符号 c 的判断不构成 if-else-if 关系，因为当 i=s.size()-1 的时候，需要处理最后一个数字。即，c 是数字且是最后一个字符的情况下，需要经过这两个分支的处理。

右括号就比较烦人，因为括号的优先级高于一切，需要找到最内部的括号，逐层往外回退得到答案。而这，也让人容易联想到传说中的递归。

那么递归需要记录关于括号的哪些东西呢？想法自然是遇到一个左括号，那么就计算括号内部的东西，遇到右括号返回。之后跳过括号里面的内容，计算下一个表达式。括号中的括号也是同理。我们来看程序：

class Solution {
public:
    int calculate(string s) {
        int idx = 0;
        return subcal(s, idx);
    }
    int subcal(string s, int& idx) {
        int num = 0;
        char sign = '+';
        stack<int> stk;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (isdigit(c))
                num = 10 * num + (c - '0');
            if (c == '(') {
                num = subcal(s.substr(i+1), idx);
                i += (idx + 2);
                c = s[i];
            }
            if (!isdigit(c) && c != ' ' || i == s.size() - 1) {
                if (sign == '+')
                    stk.push(num);
                else if (sign == '-')
                    stk.push(-num);
                else if (sign == '*') {
                    auto tmp = stk.top();
                    stk.pop();
                    stk.push(num * tmp);
                }
                else if (sign == '/') {
                    auto tmp = stk.top();
                    stk.pop();
                    stk.push(tmp / num);
                }
                sign = c;
                num = 0;
            }
            if (c == ')') {
                idx = i;
                break;
            }
        }
        int res = 0;
        while(stk.size()) {
            res += stk.top();
            stk.pop();
        }
        return res;
    }
};

同样来解读一下：

  • 如果遇到右括号，记录索引，表示当前括号的内容计算完了，退出。
  • 如果遇到左括号，那么计算左括号后面子串的内容得到数字，i=i+(idx+2) 的意思是，跳到右括号后面第一个字符继续计算，+2 为什么是后面第一个字符呢？因为 substr(i+1) 了，这里向后移动了一位，对于 i 来说，+2 才是后面的第一位。

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK