2024表达式求值

P06330. 表达式求值

Description
一个数学表达式由下列元素组成：左括号，右括号，加号，减号，乘号，正号，负号，整数（无前导０）。

给出一个长度不超过100的数学表达式，求它的值，要求考虑括号和乘法的优先级，计算过程中的临时值的绝对值保证不会超过整数范围 。

给出的表达式保证合法以及符合人的书写习惯（但可能会有多余的括号对），没有空格符号。

以下表达式被认为是合法的：

((10+(-100))) ，-3*(+5+72)-(0) ，-0 ，(-3)(-5+7)。

以下表达式被认为非法：1+-7 ，--3+8 ，-3+() 。

Format
Input
一行，给出一个合法的表达式。

Output
如题

Samples
输入数据 1
-3*(+5-7*2)-(0)
输出数据 1
27

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
int m;
char ch[200];
char str[200];
void eval() {
	// 由于栈先进后出的性质，a为倒数第二个数，b为倒数第一个数，因为顺序回影响减法和除法
	int b = num.top();
	num.pop();
	int a = num.top();
	num.pop();
	int c = op.top();
	op.pop();
	int x;
	if(c == '+') x = a + b;
	else if(c == '-') x = a - b;
	else if(c == '*') x = a * b;
	else x = a / b;
	num.push(x);
}
int main() 
{
	unordered_map<char, int> pr {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; // 优先级
	cin >> ch + 1;
	int len = strlen (ch + 1);
	ch[0] = '(';
	ch[len + 1] = ')';
	//给输入原字符串最外层加上一对左右括号 
	m=0;
	for (int i = 0; i <= len+1; i ++) 
	//对于充当正负号的"+","-"，在它的前面加个数字0 
	{
		if (ch[i - 1] == '(' && (ch[i] == '-' || ch[i] == '+'))
			str[++ m] = '0';
		str[++ m] = ch[i];
	}
	for(int i = 1; i <=m; i ++) 
	{
		char c = str[i];
		if(isdigit(c)) //如果输入的是一个数字字符，将其转成一个数字 
		{
			int j = i, x = 0;
			while(j <m&& isdigit(str[j]))
				x = x * 10 + str[j ++] - '0';
			i = j - 1; // 更新i的位置
			num.push(x);
		} 
		else 
		    if(c == '(') //如果是左括号，直接进栈 
			  op.push(c);
		    else 
			    if(c == ')') //如果是右括号，其比所有运算符的级别都要低，于是不断进行运算
				//直到遇到一个左括号 
			    {
			          while(op.top() != '(')
			          	   eval();
			          op.pop(); // 把'('pop掉
		        } 
				else 
				//既不是数字字符，也不是左右括号，其必然为运算符 
				    {
			              while(op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) 
			              //只要放在运算符栈顶的运算符级别高于当前读入的字符
						  //则可取出运算符栈顶的运算符与数字所在栈顶的两个数字进行相关运算 
						       eval();
			              op.push(c);  //将当前字符加入运算符栈 
		            }
	}
	cout << num.top() << endl;
	return 0;
}