【模板题】模拟栈，表达式求值

【题目描述】
实现一个栈，栈初始为空，支持四种操作：

• push x – 向栈顶插入一个数x；
• pop – 从栈顶弹出一个数；
• empty – 判断栈是否为空；
• query – 查询栈顶元素。

现在要对栈进行 M M M个操作，其中的每个操作 3 3 3和操作 4 4 4都要输出相应的结果。

【输入格式】
第一行包含整数 M M M，表示操作次数。
接下来 M M M行，每行包含一个操作命令，操作命令为push x，pop，empty，query中的一种。

【输出格式】
对于每个empty和query操作都要输出一个查询结果，每个结果占一行。
其中，empty操作的查询结果为YES或NO，query操作的查询结果为一个整数，表示栈顶元素的值。

【数据范围】
1 ≤ M ≤ 100000 1≤M≤100000 1≤M≤100000
1 ≤ x ≤ 1 0 9 1≤x≤10^9 1≤x≤109
所有操作保证合法。

【输入样例】

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

【输出样例】

5
5
YES
4
NO

【代码】

#include 
#include 
using namespace std;

const int N = 100010;
int m;
int stk[N], tt;

int main()
{
	cin >> m;
	while (m--)
	{
		string op;
		int x;
		cin >> op;
		if (op == "push")
		{
			cin >> x;
			stk[++tt] = x;
		}
		else if (op == "pop") tt--;
		else if (op == "query") cout << stk[tt] << endl;
		else cout << (tt > 0 ? "NO" : "YES") << endl;
	}
	return 0;
}

【题目描述】
给定一个表达式，其中运算符仅包含+,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。
注意：

• 数据保证给定的表达式合法。
• 题目保证符号-只作为减号出现，不会作为负号出现，例如，-1+2，(2+2)*(-(1+1)+2)之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 2 31 − 1 2^{31}−1 231−1。
• 题目中的整除是指向 0 0 0取整，也就是说对于大于 0 0 0的结果向下取整，例如 5 / 3 = 1 5/3=1 5/3=1，对于小于 0 0 0 的结果向上取整，例如 5 / ( 1 − 4 ) = − 1 5/(1−4)=−1 5/(1−4)=−1。
• C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

【输入格式】
共一行，为给定表达式。

【输出格式】
共一行，为表达式的结果。

【数据范围】
表达式的长度不超过 1 0 5 10^5 105。

【输入样例】

(2+2)*(1+1)

【输出样例】

8

【代码】

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

string str;
stack num;
stack op;
unordered_map pr{ {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };

void eval()
{
	int b = num.top(); num.pop();
	int a = num.top(); num.pop();
	char 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 num.push(a / b);
}

int main()
{
	cin >> str;
	for (int i = 0; i < str.size(); i++)
	{
		char c = str[i];
		if (isdigit(c))
		{
			int x = 0, j = i;
			while (j < str.size() && isdigit(str[j]))
				x = x * 10 + str[j++] - '0';
			i = j - 1;
			num.push(x);
		}
		else if (c == '(') op.push(c);
		else if (c == ')')
		{
			while (op.top() != '(') eval();
			op.pop();
		}
		else
		{
			while (op.size() && pr[op.top()] >= pr[c]) eval();
			op.push(c);
		}
	}
	while (op.size()) eval();
	cout << num.top() << endl;
	return 0;
}