【3.10】LeetCode每日一题· 基本计算器

2021年03月10日 12时49分

标签： LeetCode 栈

## 题目描述
实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。

#### 示例1
	输入：s = "1 + 1"
	输出：2

#### 示例2
	输入：s = " 2-1 + 2 "
	输出：3

#### 示例3
	输入：s = "(1+(4+5+2)-3)+(6+8)"
	输出：23

#### 提示
	1 <= s.length <= 3 * 105
	s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
	s 表示一个有效的表达式

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接]

## 解题思路
由于表达式仅由+和-构成，因此如果将表达式中所有的括号展开，那么所有数字本身都不会发生变化，只有每个数字前的符号会发生变化。
因此，使用一个取值为$$\\{-1, +1\\}$$的整数`sign`来表示当前遍历到的数字之前（在去掉所有括号的展开式中）的符号。那么`sign`的取值为：
1. 当前数字（在未去掉括号的展开式中）的前一个符号；
2. 如果当前数字处于一系列括号之内，那么每当一个括号之前为`-`号，sign的符号需要被翻转一次。
因此，可以维护一个栈，栈顶元素记录了当前位置之前的每个括号之前的符号所【共同形成】的符号。当每遇到一个`(`时，就将当前`sign`压入栈中；当遇到`)`时，就将栈顶元素弹出。

## 代码
	class Solution {
	public:
		int calculate(string s) {
			stack<int> ops;
			ops.push(1);
			int sign = 1;
			int res = 0, i = 0;
			while(i < s.length()){
				if(s[i] == ' '){
					i++;
				}else if (s[i] == '+'){
					sign = ops.top();
					i++;
				}else if (s[i] == '-'){
					sign = ops.top() * -1;
					i++;
				}else if (s[i] == '('){
					ops.push(sign);
					i++;
				}else if (s[i] == ')'){
					ops.pop();
					i++;
				}else{
					int temp = 0;
					while(i < s.length() && s[i] >= '0' && s[i] <= '9'){
						temp *= 10;
						temp += s[i]-'0';
						i++;
					}
					res += sign*temp;
				}
			}
			return res;
		}
	};

## 用时和内存
> 执行用时：12 ms，在所有 C\++提交中击败了71.50%的用户
> 内存消耗：7.9 MB，在所有 C\++提交中击败了84.97%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.10】LeetCode每日一题· 基本计算器

所有评论

暂无评论

新增评论