题目传送门

题目描述

给出一个表达式,其中运算符仅包含$+,-,\ast ,/,$^（加 减 乘 整除 乘方）要求求出表达式的最终值。

数据可能会出现括号情况，还有可能出现多余括号情况。

数据保证不会出现大于或等于$2^{31}$的答案。

数据可能会出现负数情况。

输入格式

输入仅一行，即为表达式。

输出格式

输出仅一行，既为表达式算出的结果。

输入样例：

(2+2)^(1+1)

输出样例：

16

题解

计算表达式的值也是经典的用栈来解决的问题
我们首先进行讲解

我们平时使用的表达式，都是最常见的中缀表达式（即A op B的形式），例如：$3\ast (1-2)$
栈并不能直接求得中缀表达式的计算结果，但可以求得后缀表达式（即A B op）的结果
在后缀表达式中，我们无需判断符号间的先后顺序，只需要进行以下操作：
1.当遇到数字时，把它压入栈
2.当遇到符号时，把栈顶的两个元素弹出并记录，进行计算，再将计算结果压回栈
第二步中要注意减法与除法是不满足交换律的，要注意不要将两个数颠倒了

code

#include<bits/stdc++.h>
using namespace std;
stack<int> s;
int main()
{
	string a;
	cin>>a;
	for(int i=0;i<a.size();i++)
	{
		if(a[i]>='0'&&a[i]<='9') s.push(a[i]-'0');
		else
		{
			int y=s.top();s.pop(); 
			int x=s.top();s.pop(); 
			if(a[i]=='+') s.push(x+y);
			if(a[i]=='-') s.push(x-y);
			if(a[i]=='*') s.push(x*y);
			if(a[i]=='/') s.push(x/y);
		} 
	}
	cout<<s.top(); 
	return 0;
}

当然，上述代码只针对于一位数字有效，如果有多位数的话就需要再进行额外的处理将其转化为整数

现在我们已经知道了后缀表达式如何计算，为了求得中缀表达式的结果，我们可以将中缀表达式转化为后缀表达式，具体的实现过程如下：
1.如果遇到数字，输出该数字
2.如果遇到左括号，将左括号入栈
3.如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后把左括号出栈
4.如果遇到运算符，只要栈顶符号的优先级不低于新符号，就不断取出栈顶并输出，最后把新符号入栈。优先级为乘除>加减>左括号

最终将栈的元素全部取出，得到的结果即为后缀表达式

讲解一下上述操作的原理，我们从第四步说起
当输入一个符号op，在中缀表达式中， b是在op之后输入的，但在后缀表达式中，我们要将它提到op之前，但b之前还要先解决a的问题，我们要考虑到，a可能不仅仅为一个简单的数字，它可能是一个表达式算出的结果$(1+2)\ast 3$，例如上述例子中乘号左边对应的a为$(1+2)$，所以就需要把优先级不低于op的式子进行计算，也就有了第四步中输出符号不低于op的所有符号

我们不需要去额外考虑数字的输出顺序，只要有数字，我们就将其输出，因为我们只需要考虑这种顺序中如何插入符号，使其变为后缀表达式即可，而插入符号的过程，就是上述所讲述的过程

自己手动推几组转化过程，仔细体会过程

这道题目其实就是一道裸的中缀表达式求解，但难点在于以下几点：
1.数字中存在多位数
2.存在多余括号的情况
3.会出现负数
对这些操作我们逐个进行讲解

首先是存在多位数，可以执行一个操作，将连续的数字的两头都加上一个空格，也就是使这个数字与其他任何符号都隔离开来，以便于我们将这个数从字符提取为整数

多余括号的问题也不难解决
左括号冗余：这些左括号会在最后一步被统一压入后缀表达式中，但由于后缀表达式中是不存在左括号的，所以我们在求解后缀表达式时，直接将左括号忽略即可
右括号冗余：在括号能完全匹配的情况下，右括号一定能在它前面找到与它匹配的左括号，所以不需要判断栈顶是否为空，但右括号冗余就可能找不到与之匹配的左括号，因此要在找左括号的过程中加上判断栈顶是否为空的条件

出现负数的情况是最棘手的
分为两种情况，如果这个负号前有具体的数字a，那就不需要考虑负数的影响，但如果不存在a，例如-1或2+（-1+3），为了避免计算后缀表达式时出错，我们在前面加上一个0，将其变为0-1，这样就可以解决这个问题啦

code

#include<bits/stdc++.h>
using namespace std;
string s,ss;
stack<char> fh;
stack<int> shu;
int main()
{
	bool ff=0;
	cin>>s;
	int len=s.size();
	for(int i=0;i<len;i++)//中缀表达式转后缀表达式
	{
		if(s[i]>='0'&&s[i]<='9') 
		{ 
			ff=1;//存在a，不需要填0
			ss+=s[i];
			if(s[i+1]<'0'||s[i+1]>'9') ss+=' ';//处理多位数
		}
		if(s[i]=='(')
		{
			ff=0;//左括号的优先级高，会忽略前面是否有数字
			fh.push(s[i]);
		}
		if(s[i]==')')
		{
			while(fh.size()&&fh.top()!='(')//右括号冗余特判
			{
				ss+=fh.top();
				fh.pop();
			}
			if(fh.size()) fh.pop();
		}
		if(s[i]=='^')
		{
			while(fh.size()&&fh.top()!='*'&&fh.top()!='/'&&fh.top()!='+'&&fh.top()!='-'&&fh.top()!='(')
			{
				ss+=fh.top();
				fh.pop();
			}
			fh.push(s[i]);
		}
		if(s[i]=='*'||s[i]=='/')
		{ 
			while(fh.size()&&fh.top()!='+'&&fh.top()!='-'&&fh.top()!='(')
			{
				ss+=fh.top();
				fh.pop();
			}
			fh.push(s[i]);
		}
		if(s[i]=='+'||s[i]=='-')
		{
			if(s[i]=='-'&&!ff) ss+="0 ";//加0，处理负号
			while(fh.size()&&fh.top()!='(')
			{
				ss+=fh.top();
				fh.pop();
			}
			fh.push(s[i]);
		}
	}
	while(fh.empty()==0)
	{
		ss+=fh.top();
		fh.pop();
	} 
	int len1=ss.size(),shu1=0;
	for(int i=0;i<len1;i++)//计算后缀表达式的值
	{
		if(ss[i]==' '||ss[i]=='(') continue;//处理左括号冗余情况
		else if(ss[i]>='0'&&ss[i]<='9') //处理多位数
		{
			shu1=shu1*10+ss[i]-'0';
			if(ss[i+1]==' ')
			{
				shu.push(shu1);
				shu1=0;
			}
		}
		else 
		{
			int y=shu.top();
			shu.pop();
			int x=shu.top();
			shu.pop();
			if(ss[i]=='+') shu.push(x+y);
			if(ss[i]=='-') shu.push(x-y);
			if(ss[i]=='/') shu.push(x/y);
			if(ss[i]=='*') shu.push(x*y);
			if(ss[i]=='^') shu.push(pow(x,y));
		}
	}
	cout<<shu.top();
	return 0;
}