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

2021年03月11日 10时42分

标签： LeetCode 栈

## 题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。

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

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

#### 示例3
	输入：s = " 3+5 / 2 "
	输出：5

#### 提示
	1 <= s.length <= 3 * 10^5
	s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
	s 表示一个 有效表达式
	表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
	题目数据保证答案是一个 32-bit 整数

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/basic-calculator-ii/ "题目链接")

## 解题思路
双栈法，采用一个数字栈，一个符号栈。对输入字符串进行遍历，如果遍历到数字，则直接压入数字栈中，否则根据符号栈的栈顶元素和当前遍历到的运算符的优先级关系，确定采取的动作：
1. 如果当前符号较符号栈顶元素优先级**更高**，则入栈；
2. 如果当前符号较符号栈顶元素优先级**相同**，或**更低**，则从数字栈中弹出两个元素，并弹出符号栈顶元素，进行运算，将运算结果重新压入数字栈中。重复入上过程直到**符号栈顶元素优先级小于当前符号（或符号栈为空）**为止。

在这里，元素的优先级即为运算的优先级，有*****等于**/**大于**+**等于**-**。

由于本题的表达式不包含括号，如果包含括号，那么该如何处理呢（见[基本计算器 III](https://leetcode-cn.com/problems/basic-calculator-iii/ "基本计算器 III")）？
考虑同样的元素优先级不变，但是需要对遇到括号的情况进行特殊处理。具体地说，当我们遇到左括号`(`时，一定将其压入符号栈中，并且当栈顶元素为左括号`(`时，不管当前遍历到的符号为什么，都需要将其压入符号栈中（由于左括号相当于一个新的表达式开始）。而当遇到右括号`)`时，需要不断弹出符号栈，直到遇到左括号`(`为止，然后弹出左括号`(`（右括号不入栈，相当于计算括号中的一个子表达式）。
因此，我们可以得出包含括号的算术表达式的代码。

## 代码
	class Solution {
	public:
		int prior(char now, char top){
			if(top == '('){
				return true;
			}else if(now == '+' || now == '-'){
				return false;
			}else if((now == '*' || now == '/') && (top == '+' || top == '-')){
				return true;
			}else{// if((now == '*' || now == '/') && (top == '*' || top == '/')){
				return false;
			}
		}

long long cal(long long num1, long long num2, char opr){
			switch(opr){
				case '+':{
					return num1 + num2;
				}
				case '-':{
					return num1 - num2;
				}
				case '*':{
					return num1 * num2;
				}
				case '/':{
					return num1 / num2;
				}
				default:{
					return -1;
				}
			}
		}

int calculate(string s) {
			stack<char> op;
			stack<long long> nums;
			s.push_back(')');
			s.insert(s.begin(), '(');
			for(int i = 0; i < s.length(); i++){
				if(s[i] == ' ') continue;
				if(s[i] == '('){
					op.push('(');
				}else if(s[i] == ')'){
					while(op.top() != '('){
						char opr = op.top(); op.pop();
						long long num2 = nums.top(); nums.pop();
						long long num1 = nums.top(); nums.pop();
						nums.push(cal(num1, num2, opr));
					}
					op.pop();
				}else if(s[i] >= '0' && s[i] <= '9'){
					long long res = 0;
					while(i < s.length() && s[i] >= '0' && s[i] <= '9'){
						res *= 10;
						res += s[i] - '0';
						i++;
					}
					nums.push(res);
					i--;
				}else{
					while(!prior(s[i], op.top())){
						char opr = op.top(); op.pop();
						long long num2 = nums.top(); nums.pop();
						long long num1 = nums.top(); nums.pop();
						nums.push(cal(num1, num2, opr));
					}
					op.push(s[i]);
				}
			}
			return nums.top();
		}
	};

## 用时和内存
基本计算器 II
> 执行用时：16 ms，在所有 C\++提交中击败了55.76%的用户
> 内存消耗：8 MB，在所有 C\++提交中击败了80.85%的用户

基本计算器 III
> 执行用时：0 ms，在所有 C\++提交中击败了100.00%的用户
> 内存消耗：6.5 MB，在所有 C\++提交中击败了90.80%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

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

所有评论

暂无评论

新增评论