首页 > 技术文章 > LeetCode "Basic Calculator"

tonix 2015-06-09 13:41 原文

My first try was DFS by intuition, but it ended up with MLE. So, the expected solution is to use stack:

class Solution {
    struct Node
    {
        Node(int _v) : v(_v), isNum(true){}
        Node(char b) : brack(b), isNum(false){}
        bool isNum;
        int v;
        char brack;
    };
public:
    void eval(vector<Node> &operands, vector<char> &ops)
    {
        while (operands.size() > 1 && operands.back().isNum && operands[operands.size() - 2].isNum
            && ops.size() > 0)
        {
            char c = ops.back(); ops.pop_back();
            int v0 = operands.back().v; operands.pop_back();
            int v1 = operands.back().v; operands.pop_back();
            int ret;
            if (c == '+') ret = v1 + v0;
            if (c == '-') ret = v1 - v0;
            operands.push_back(ret);
        }
    }
    int calculate(string s) 
    {
        string ss;
        for (auto c: s)
        if (c != ' ') ss += c;

        vector<Node> operands;
        vector<char> ops;

        size_t len = ss.length();
        int i = 0;
        int operand = 0;
        while (i < len)
        {
            char c = ss[i];
            if (isdigit(c))
            {
                operand *= 10;
                operand += c - '0';
                if (((i + 1) < len && !isdigit(ss[i + 1])) ||
                    (i + 1) == len)
                {
                    operands.push_back(operand);
                    eval(operands, ops);
                    operand = 0;
                }
            }
            else if (c == '+' || c == '-')
            {
                ops.push_back(c);
            }
            else if (c == '(')
            {
                operands.push_back(Node('('));
            }
            else if (c == ')')
            {
                int v = operands.back().v; operands.pop_back();
                char b = operands.back().brack; operands.pop_back();
                operands.push_back(v);
                eval(operands, ops);
            }
            i++;
        }

        return operands[0].v;
    }
};

推荐阅读