【栈】224. 基本计算器

本文涉及知识点

栈

LeetCode 224. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 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 * 10⁵
s 由数字、‘+’、‘-’、‘(’、‘)’、和 ’ ’ 组成
s 表示一个有效的表达式
‘+’ 不能用作一元运算(例如， “+1” 和 “+(2 + 3)” 无效)
‘-’ 可以用作一元运算(即 “-1” 和 “-(2 + 3)” 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位 整数

栈

由于只有 加、减、负号，所有不需要操作数栈，只需要操作符栈，±(三种。数值直接运算。

操作数

当前栈，负号的总数为偶数，则将当前数值加到结果，否则从结果中减去当前值。
如果当前栈顶为±，出栈。

左括号、+、-

入栈

右括号

出栈括号，及前面的±号。

注意：cnt 记录栈中负号的数量。

代码

核心代码

class Solution {
public:
	int calculate(string s) {
		int iRet = 0;
		for (int i = 0; i < s.length(); i++) {
			if (' ' == s[i]) { continue; }
			if (('(' == s[i]) || ('+' == s[i])) {
				m_sta.emplace(s[i]);
			}
			else if('-' == s[i]) {
				m_sta.emplace(s[i]);
				m_iCnt++;
			}
			else if (')' == s[i]) {
				m_sta.pop();
				PopSign();
			}
			else {
				int num = 0;
				while (isdigit(s[i])) {
					num = 10 * num + (s[i] - '0');
					i++;
				}
				if (1 & m_iCnt) {
					iRet -= num;
				}
				else {
					iRet += num;
				}
				PopSign();
				i--;
			}
		}
		return iRet;
	}
	void PopSign() {
		if (m_sta.empty() || ('(' == m_sta.top())) { return; }
		if ('-' == m_sta.top()) { m_iCnt--; };
		m_sta.pop();
	}
	stack<char> m_sta;
	int m_iCnt = 0;
};

单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1 , t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());	
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{
	string s;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod0)
		{	
			s = "1 + 1";
			auto res = Solution().calculate(s);
			AssertEx(2,res);
		}
		TEST_METHOD(TestMethod1)
		{
			s =" 2-1 + 2 ";
			auto res = Solution().calculate(s);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod2)
		{
			s = "(1+(4+5+2)-3)+(6+8)";
			auto res = Solution().calculate(s);
			AssertEx(23, res);
		}
		TEST_METHOD(TestMethod3)
		{
			s = "2147483647";
			auto res = Solution().calculate(s);
			AssertEx(2147483647, res);
		}

		
	};
}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。