• LintCode 978: Basic Calculator 栈好题

    978 · Basic Calculator
    Algorithms
    Medium

    Description
    Implement a basic calculator to evaluate a simple expression string.

    The expression string may contain open ‘(’ and closing parentheses ‘)’, the plus ‘+’ or minus sign ‘-’, non-negative integers and empty spaces ’ '.

    You may assume that the given expression is always valid.

    Do not use the eval built-in library function.

    Example
    Example 1

    Input：“1 + 1”
    Output：2
    Example 2

    Input：“(1+(4+5+2)-3)+(6+8)”
    Output：23
    Tags
    Company
    Airbnb
    Facebook
    Google
    Related Problems

    424
    Evaluate Reverse Polish Notation
    Medium

    849
    Basic Calculator III
    Hard

    980
    Basic Calculator II
    Medium

    解法1：先tokenize，然后转换成逆波兰表达式RPN，再处理RPN，跟LintCode 424一样的方法。
    注意：
    1.我们常用的容易阅读的表达式1+2*3是中序遍历
    2. 逆波兰表达式是1 2 3 *＋是后序遍历
    3. 波兰表达式是＋1 * 2 3是前序遍历

    波兰和逆波兰有个好处就是不需要括号。

    class Solution {
public:
    /**
     * @param s: the given expression
     * @return: the result of expression
     */
    int calculate(string &s) {
        int len = s.size();
        vector<string> tokens;
        
        //tokenize
        int pos = 0, orig_pos = 0;
        while (pos < len) {
            while (pos < len && s[pos] == ' ') pos++;
            if (pos == len) break;
            orig_pos = pos;
            if (!isdigit(s[pos])) {
                tokens.push_back(s.substr(pos, 1));
                pos++;
            }
            else {
                while(pos < len && isdigit(s[pos])) pos++;
                tokens.push_back(s.substr(orig_pos, pos - orig_pos));
            }
            
        }

        //generate RPN
        len = tokens.size();
        stack<string> optrStk;
        vector<string> RPN;
        map<string, int> prio;
        prio["+"] = 1;
        prio["-"] = 1;
        prio["*"] = 2;
        prio["/"] = 2;

        for (int i = 0; i < len; i++) {
            string token = tokens[i];
            if (token.size() > 1 || (token[0] >= '0' && token[0] <= '9')) {
                RPN.push_back(token);
                continue;
            }
            if (token == "(") {
                optrStk.push(token);
                continue;
            }
            if (token == ")") {
                while (!optrStk.empty() && optrStk.top() != "(") {
                    RPN.push_back(optrStk.top());
                    optrStk.pop();
                }
                optrStk.pop();  //pop "("
                continue;
            }
            while (!optrStk.empty() && prio[optrStk.top()] >= prio[token]) {
                RPN.push_back(optrStk.top());
                optrStk.pop();
            }
            optrStk.push(token);
        }
        //dump the rest in optrStr to RPN
        while (!optrStk.empty()) {
            RPN.push_back(optrStk.top());
            optrStk.pop();
        }

        //process RPN
        stack<int> RPNStk;
        len = RPN.size();
        if (len == 0) return 0;
        if (len == 1) return stoi(RPN[0]);
        for (int i = 0; i < len; i++) {
            string token = RPN[i];
            if (token.size() > 1 || (token[0] >= '0' && token[0] <= '9')) {
                RPNStk.push(stoi(token));
                continue;
            } else {
                int top1 = RPNStk.top(); RPNStk.pop();
                int top2 = RPNStk.top(); RPNStk.pop();
                int result = 0;
                switch (RPN[i][0]) {
                    case '*': result = top2 * top1; break;
                    case '/': result = top2 / top1; break;
                    case '+': result = top2 + top1; break;
                    case '-': result = top2 - top1; break;
                    default: break;
                }
                RPNStk.push(result);
            }
        }
        return RPNStk.top();
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94

    解法2：参考的九章的解法，我觉得很不错。原文如下:
    "
    我们需要三个变量和一个栈: number表示当前的操作数, sign表示当前的操作数应该被加还是被减, result表示结果.
    初始number, result = 0, sign = 1, 开始遍历字符串:
    碰到数字则追加到number尾端
    碰到加号说明上一个数字已经完全被计算至number, 这时应该把number * sign加到result中, 然后把sign置为1 (因为当前碰到了加号)
    碰到减号, 同上, 不同的在于最后要把sign置为-1
    碰到左括号, 说明这时要优先出右边的表达式, 需要将result和sign压入栈中(注意, 此时的sign表示的是这个括号内的表达式应该被result加上还是减去), 然后初始化result和sign, 准备计算括号内的表达式
    碰到右括号, 说明一个括号内的表达式被计算完了, 此时需要从栈中取出该括号之前的sign和result, 与当前的result相加运算 (注意, 是原来的result + sign * 当前result)
    注意, 一个合法的表达式, 左括号之前一定不会是数字, 右括号之前一定是一个数字. 所以碰到右括号不要忘了先把number * sign加到当前result里.
    以及, 循环结束后number可能还有数字, 需要加到result里. (比如"1+2"这样的表达式, 2并不会在循环内被加到结果中)
    "

    class Solution {
public:
    /**
     * @param s: the given expression
     * @return: the result of expression
     */
    int calculate(string &s) {
        int len = s.size();
        stack<int> stk;
        int res = 0, num = 0;
        int sign = 1;
        for (char c : s) {
            if (isdigit(c)) {
                num = num * 10 + c - '0';
                continue;
            }
            if (c == '+' || c == '-') {
                res += num * sign;
                num = 0;
                sign = (c == '+') ? 1 : -1;
                continue;
            }
            if (c == '(') {
                stk.push(res);
                stk.push(sign);
                sign = 1;
                res = 0;
                continue;
            }
            if (c == ')') {
                res += sign * num;
                int saved_sign = stk.top(); stk.pop();
                int saved_res = stk.top(); stk.pop();
                res = saved_res + saved_sign * res;
                num = 0;
                //sign = 1;
            }
        }
        if (num != 0) {
            res += sign * num;
        }
        return res;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    解法3：在解法2的基础上，我们可以在括号之间用递归，这里我们必须要确定左括号的个数和右括号的个数相等时，其内部才是一个完整的表达式，因此可以用递归，这里就是用系统栈来代替栈。

    class Solution {
public:
    /**
     * @param s: the given expression
     * @return: the result of expression
     */
    int calculate(string &s) {
        int len = s.size();
        stack<int> stk;
        int res = 0, num = 0;
        int sign = 1;
        int bracket_cnt = 0;
        int i = 0;
        while (i < len) {
            char c = s[i];
            if (isdigit(c)) {
                num = num * 10 + c - '0';
            }
            else if (c == '+' || c == '-') {
                res += num * sign;
                num = 0;
                sign = (c == '+') ? 1 : -1;
            }
            else if (c == '(') {
                int orig_pos = i + 1;
                bracket_cnt = 1;
                while (i < len && bracket_cnt > 0) {
                    i++;
                    if (s[i] == '(') bracket_cnt++;
                    else if (s[i] == ')') bracket_cnt--;
                }
                
                string s2 = s.substr(orig_pos, i - orig_pos);
                int temp_res = calculate(s2);
                res += sign * temp_res;
                num = 0;
            }
            i++;
        }
        if (num != 0) {
            res += sign * num;
        }
        return res;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    解法4：参考的labuladong的解法。跟解法3差不多。
    注意：
    helper()里面的index必须用&，因为递归回来后，index的值就已经递增了。
    递归完后，c=s[index]是更新后的index对应的字符。
    如果不是最后一个字符，遇到运算符(非数字又非空格)，要进switch()处理。如果是最后一个字符，不管是什么(空格也好，数字也好)，也要进switch()处理，不然这最后一个数字就丢掉了。

    class Solution {
public:
    int calculate(string s) {
        int index = 0;
        return helper(s, index);
    }
private:
    int helper(string &s, int &index) {
        stack<int> stk;
        int sLen = s.size();
        char sign = '+';
        int num = 0;
        int res = 0;
        for (; index < sLen; index++) {
            char c = s[index];
            if (c == '(') {
                index++;
                num = helper(s, index);
            }
            c = s[index];
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } 
            if ((!isdigit(c) && c != ' ') || index == sLen - 1) { //(c == '+' || c == '-' || c == '*' || c == '/') or reach the end
                switch (sign) {
                    case '+':
                        stk.push(num);
                        break;
                    case '-':
                        stk.push(-num);
                        break;
                    case '*':
                        stk.push(stk.top() * num);
                        stk.pop();
                        break;
                    case '/':
                        stk.push(stk.top() / num);
                        stk.pop();
                        break;
                    default:
                    break;
                }
                sign = c;
                num = 0;
            }
            if (c == ')') {
                index++;
                break;
            }
        }
        
        while (!stk.empty()) {
            res += stk.top();
            stk.pop();
        }
        return res;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    二刷：跟上面差不多，用vector而不是stack。

    class Solution {
public:
    /**
     * @param s: the given expression
     * @return: the result of expression
     */
    int calculate(string &s) {
        int index = 0;
        return calExpr(s, index);
    }
private:
    int calExpr(string &s, int &index) {
        int num = 0;
        char sign = '+';
        vector<int> res;
        while (index < s.size()) {
            if (s[index] == '(') {
                index++;
                num = calExpr(s, index);
                //res.push_back(sign * num); //不能push_back，要等到+-*/或index==s.size()-1再push_back
            }
            if (isdigit(s[index])) {
                num = num * 10 + (s[index] - '0');
                //不能continue，也不能index++, 因为可能最后一个字符就是数字
                //也不能push_back()，要等到+-*/或index==s.size()-1再push_back
            } 
            if ((!isdigit(s[index]) && s[index] != ' ')|| index == s.size() - 1) {
                if (sign == '+') {
                    res.push_back(num);
                } else if (sign == '-') {
                    res.push_back(-num);
                }
                sign = s[index];
                num = 0;
               // index++;
            }
            
            if (s[index] == ')') {
                index++; //这里要加index++，因为马上要break
                break;
            }
            index++;
        }
        int sum = 0;
        for (auto n : res) {
            sum += n;
        }
        return sum;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
  • 相关阅读:
    Android优化篇|网络预连接
    药智网数据库介绍
    SolidWorks三维机械设计软件超实用操作技巧（九）
    Harbor企业级私服Docker镜像仓库搭建及应用
    LeetCode--回文数
    JS模块化
    DevOps统一管控平台调研
    计算机毕业设计 基于SpringBoot大学生就业服务平台的设计与实现 Javaweb项目 Java实战项目 前后端分离 文档报告 代码讲解 安装调试
    spring ExpressionParser 四则运算表达式解析参数提取
    秋招如何准备？有什么建议？
  • 原文地址：https://blog.csdn.net/roufoo/article/details/127553467