leetcode--227 基本计算器II 数据栈 符号栈

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数,+-*/ 四种运算符和空格  。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 7

示例 2:

输入: " 3/2 "
输出: 1

示例 3:

输入: " 3+5 / 2 "
输出: 5

说明:

  • 你可以假设所给定的表达式都是有效的。
  • 不要使用内置的库函数 eval

解题思路:一般需要符号栈、数据栈,两个。但是,看到网上一个写的不错的算法,只用了一个数据栈。符号栈用一个变量sign代替了,只存储上一个符号,主要思想如下:

  1. 将减法转化为加法(取相反数)
  2. 由于乘除法优先级高,直接计算
  3. 整数不仅一位,会>10
  4. 表达式中没有括号

注意:

传送门:

int leetcode_array::calculate(string s)
{
	//一般的解题思路要用到符号栈 数据栈
	int result = 0;

	char sign = '+';  //记录当前符号
	stack<int> data_stack;
	stack<char> sign_stack;
	int number = 0;
	for (int i = 0; i < s.size(); ++i)
	{
		//注意'+'43, '-':45,‘*':42,'/': 47对应的ascII值都小于‘0’, 'space': 32
		if (s[i] >= '0')
		{
			number = number * 10 - '0' + +s[i];  //先减后加,避免溢出

			/*if (s[i + 1] < '0'){
				data_stack.push(number);
				number = 0;
			}*/
		}
		
		//确保得到有效符号
		if ((s[i] < '0' && s[i] != ' ' )|| i == s.size() - 1)
		{
			if (sign == '*'||sign == '/'){    //sign是上一个符号
				//遇到'*' '/'应直接进行计算
				int tmp = sign=='*'? data_stack.top()*number : data_stack.top() / number;
				data_stack.pop();
				data_stack.push(tmp);
			}
			else if (sign == '-'){
				data_stack.push(-number);
			}
			else{
				data_stack.push(number);
			}

			sign = s[i];  //注意sign保存的是当前的符号,即更新sign的符号
			number = 0;
		}

		//最后一个可能是数字或空格,但绝不是运算符
	}
	
	for (; !data_stack.empty(); data_stack.pop())
	{
		result += data_stack.top();    
	}

	return result;
}

 

;