表达式求值问题-双栈模板化实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了表达式求值问题-双栈模板化实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

好久不见，真的很久都没有更新博客了，最近很多事情，所以比较忙碌，没有时间每天都学算法，但是我会挤时间尽量做到，每两三天就更新博客，我会努力的，加油~

表达式求值问题-双栈模板化实现

前言：计算器都见过吧，我们今天要讲的就是类似于计算器计算数据的简单实现，我们需要注意一些问题，比如运算符优先级，运算顺序等等问题，话不多说，冲冲冲！！！

1.问题引入

2.问题分析及解决方法

如何设计优先级问题？

设计计算函数和启动计算条件

完整代码(可做为表达式计算模板使用）

3.金句频道

1.问题引入

表达式求值问题-双栈模板化实现

2.问题分析及解决方法

首先，我们先来看一下整体思路：对于一个表达式，我们会读入括号，运算符和数字三种字符，我们需要将这些字符区分开再进行计算，为了保证运算的正确性，由运算符带来的优先级问题是我们解决这个问题的关键，解决了运算符优先级问题，我们就可以将运算符和数字分别存入一个栈中，用读取到' ) '和读取到优先级比已经保存在栈内的运算符来作为启动计算的条件（读到右括号，我们就可以将整个括号内部的部分算出来，再将算得结果压入保存数字的栈中用于后续的计算，而对于读取到优先级低的运算符，因为我们以栈存储数据，导致我们在计算的时候就会按逆序进行计算，所以，我们每次读取到一个运算符优先级低于栈顶的字符，都要先将栈内的运算符优先级高的运算符的结果算出，从而不影响运算顺序），最后，我们的运算符栈内如果还剩下元素，直接计算即可。

如何设计优先级问题？

这里方法就有很多了，既可以用一个专门的函数来实现，也可以用STL的map键值来实现等等，这里我们采用第二种方法，该方法比较简单且代码易扩展，方便后序添加运算符。

unordered_map<char, int> p{ {'+',1},{'-',1},{'*',2},{'/',2} };//用来表示运算符的优先级，数字越大表示运算优先级越高

设计计算函数和启动计算条件

//计算函数
void f()
{
	//这里需要注意，我们的栈内保存的待运算数字和运算顺序是反着的，会影响减法和除法的计算
	auto b = num.top(); num.pop();
	auto a = num.top(); num.pop();
	auto c = op.top(); op.pop();
	if (c == '+')
		num.push(a + b);
	else if (c == '-')
		num.push(a - b);
	else if (c == '*')
		num.push(a * b);
	else if (c == '/')
		num.push(a / b);
	//如果想要再拓展其他运算，可在此处继续写下去

}

//计算启动条件
else if (s[i] == '(')//如果是左括号，直接入栈等待右括号到来再计算
			op.push(s[i]);
		else if (s[i] == ')')//右括号，准备开始计算结果
		{
			while (op.top() != '(') f();//做括号内的计算
			op.pop();//弹出左括号
		}
		else
		{
			while (!op.empty() && p[op.top()] >= p[s[i]]) f();//如果遇到优先级比前面已经入栈的运算符的优先极低的，则要先解决栈内的计算再将该优先级高的字符入栈
			op.push(s[i]);
		}

完整代码(可做为表达式计算模板使用）

#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
const int maxn = 1e5 + 10;

stack<int >num;
stack<char> op;//运算符

unordered_map<char, int> p{ {'+',1},{'-',1},{'*',2},{'/',2} };//用来表示运算符的优先级，数字越大表示运算优先级越高

void f()
{
	//这里需要注意，我们的栈内保存的待运算数字和运算顺序是反着的，会影响减法和除法的计算
	auto b = num.top(); num.pop();
	auto a = num.top(); num.pop();
	auto c = op.top(); op.pop();
	if (c == '+')
		num.push(a + b);
	else if (c == '-')
		num.push(a - b);
	else if (c == '*')
		num.push(a * b);
	else if (c == '/')
		num.push(a / b);
	//如果想要再拓展其他运算，可在此处继续写下去

}
int main()
{
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		if (isdigit(s[i]))//注意，这里需要注意10以上的数，不能只看一个字符就完了
		{
			int j = i;
			int temp = 0;
			while (j < s.size() && isdigit(s[j]))
			{
				temp = temp * 10 + s[j++] - '0';
			}
			i = j-1;//j在退出循环之前已经自增了，所以要减去
			num.push(temp);
		}
		else if (s[i] == '(')//如果是左括号，直接入栈等待右括号到来再计算
			op.push(s[i]);
		else if (s[i] == ')')//右括号，准备开始计算结果
		{
			while (op.top() != '(') f();//做括号内的计算
			op.pop();//弹出左括号
		}
		else
		{
			while (!op.empty() && p[op.top()] >= p[s[i]]) f();//如果遇到优先级比前面已经入栈的运算符的优先极低的，则要先解决栈内的计算再将该优先级高的字符入栈
			op.push(s[i]);
		}
	}
	//如果最后栈内还剩下字符，直接计算即可
	while (op.size()) f();
	printf("%d\n", num.top());

	return 0;
}

我们这里将计算函数和优先级单独设计，目的就是增加代码的可复用性，main函数内部没有涉及运算符的种类和其他的特殊处理，将特异性的功能封装成函数方便后序增添功能。