# 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

```cpp
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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/224.-basic-calculator.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.