LeetCode "Basic Calculator II"

Comparing with the 'I' one, there are two changes:

1. if last operator is "+" or "-", we don't evaluate expression
2. if last operator is "*" or "/", we evaluate it immediately, but we only pop out 2 operands.

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 singleEval(vector<Node> &operands, vector<char> &ops)
    {
        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;
        if (c == '*') ret = v1 * v0;
        if (c == '/') ret = v1 / v0;
        operands.push_back(ret);
    }
    void eval(vector<Node> &operands, vector<char> &ops)
    {
        while (operands.size() > 1 && operands.back().isNum && operands[operands.size() - 2].isNum
            && ops.size() > 0)
        {
            singleEval(operands, ops);
        }
    }
    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);
                    if (ops.size() > 0 && (ops.back() == '*' || ops.back() == '/'))
                    {
                        singleEval(operands, ops);
                    }
                    if (((i + 1) < len && ss[i + 1] != '*' && ss[i + 1] != '/')
                        || (i + 1) == len)
                        eval(operands, ops);
                    operand = 0;
                }
            }
            else if (c == '+' || c == '-' || 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++;
        }
        eval(operands, ops);
        return operands[0].v;
    }
};
原文地址:https://www.cnblogs.com/tonix/p/4593118.html