Leetcode.227.Basic Calculate II

题目

进行+-*/运算，所有数都是正数，输入会有空格。

Input: "3+2*2"
Output: 7
Input: " 3/2 "
Output: 1
Input: " 3+5 / 2 "
Output: 5

思路1

栈。将数字输入一个栈，将操作符输入一个栈。数字可能有多位数，所以需要在输入符号的时候进行运算。减法在栈里面运算会有问题，可以转化为负数的加法。

int calculate(string s) {
    stack<char> stack_op;
    stack<int> stack_num;
    bool isLastNum = false;
    for (char c : s) {
        if (c == ' ') {
            continue;
        } else if (c >= '0' && c <= '9') {
            int x = c-'0';
            if (isLastNum) {
                int num = stack_num.top();
                stack_num.pop();
                if (num > 0) {
                    x += num*10;
                } else {
                    x = num*10 - x;
                }
                stack_num.push(x);
            } else {
                if (!stack_op.empty() && stack_op.top() == '-') {
                    stack_op.pop();
                    stack_op.push('+');
                    stack_num.push(x * -1);
                } else {
                    stack_num.push(x);
                }
            }
            isLastNum = true;
        } else {
            isLastNum = false;

            if (!stack_op.empty()) {
                char op = stack_op.top();
                if (op == '*' || op == '/') {
                    int a = stack_num.top();
                    stack_num.pop();
                    int b = stack_num.top();
                    stack_num.pop();
                    stack_op.pop();
                    if (op == '*') {
                        stack_num.push(a * b);
                    }else if (op == '/') {
                        stack_num.push(b / a);
                    }
                }
            }
            if (c == '+' || c == '-') {
                while (!stack_op.empty() && stack_num.size() > 1) {
                    int a = stack_num.top();
                    stack_num.pop();
                    int b = stack_num.top();
                    stack_num.pop();
                    char op = stack_op.top();
                    if (op == '+') {
                        stack_op.pop();
                        stack_num.push(a + b);
                    } else if (op == '-') {
                        stack_op.pop();
                        stack_num.push(b - a);
                    }
                }
            }


            stack_op.push(c);
        }
    }

    while (!stack_op.empty() && stack_num.size() > 1) {
        int a = stack_num.top();
        stack_num.pop();
        int b = stack_num.top();
        stack_num.pop();
        char op = stack_op.top();
        stack_op.pop();
        if (op == '+') {
            stack_num.push(a + b);
        } else if (op == '-') {
            stack_num.push(b - a);
        }else if (op == '*') {
            stack_num.push(a * b);
        } else if (op == '/') {
            stack_num.push(b / a);
        }
    }
    
    return stack_num.top();
}

思路2

直接运算。

int calculate(string s) {
    int last = 0, cur = 0, sum = 0;
    char lastOP = '+';
    for (char c : s) {
        if (c == '+' || c == '-' || c == '*' || c == '/') {
            if (lastOP == '+') {
                sum += last;
            } else if (lastOP == '-') {
                sum += last;
                cur *= -1;
            } else if (lastOP == '*') {
                cur *= last;
            } else if (lastOP == '/') {
                cur = last / cur;
            }

            lastOP = c;
            last = cur;
            cur = 0;
        }
        if (c >= '0' && c <= '9') {
            cur = cur * 10 + c - '0';
        }
    }

    if (lastOP == '+') {
        sum += last;
    } else if (lastOP == '-') {
        sum += last;
        cur *= -1;
    } else if (lastOP == '*') {
        cur *= last;
    } else if (lastOP == '/') {
        cur = last / cur;
    }
    sum += cur;
    return sum;
}

总结

需要考虑负数运算，运算越界问题，效率问题。