224. Basic Calculator

problem 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 .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23
Note:

You may assume that the given expression is always valid. Do not use the eval built-in library function.

algorithm thought

基本计算器，只有加减法，之前数据结构学习栈的时候，提到了可以直接用两个栈解决。这学期学习编译原理课，也学到了栈式计算机，也是提供简单的栈指令可以实现计算器。

这里状态不多，不需要使用switch语句，构建DFA。直接使用if else即可。这里一共就4种类型的符号。操作符，数字，括号，括回。

这里使用一个sign符号代表当前的操作符。

碰到数字，将当前保存的数字乘10，加上这次数字 碰到操作符，因为这里没有优先级，可以直接计算上一个操作的结果，然后将sign改为这次操作对应操作符 碰到括号，将当前结果和操作符保存。括号就相当于一次递归调用函数，括号里面就是一次计算，需要保存之前的结果。 碰到括回，弹出上次保存的结果，将其与括号里的相加。

code

class Solution {
public:
    int calculate(string s) {
        stack<int> number,ops;
        int res=0,num=0,sign=1;
        for(auto&ch:s){
            if(ch==' ')
                continue;
            if(ch<='9'&&ch>='0'){
                num = num*10 + static_cast<int>(ch-'0');
            }else{
                res+=sign*num;
                num=0;
                if(ch=='+')
                    sign=1;
                else if(ch=='-')
                    sign=-1;
                if(ch=='('){
                    number.push(res);
                    res=0;
                    ops.push(sign);
                    sign=1;
                }else if(ch==')'){
                    res=res*ops.top()+number.top();
                    number.pop();ops.pop();
                }
            }
        }
        res+=sign*num;
        return res;
    }
};

algorithm analysis

只需要一次遍历字符串，时间复杂度O(n)，使用栈保存结果，最坏情况下空间复杂度O(n)