原题链接:https://www.luogu.com.cn/problem/P1981
题意解读:中缀表达式求值,只有+,*,没有括号,保留后4位。
解题思路:
中缀表达式求值的典型应用,采用两个栈:符号栈、数字栈,对于没有括号的情况,只需要如下步骤:
1、 遍历表达式每一个字符
2、如果遇到数字,则持续提取数字,保存整数到数字栈
3、如果遇到是符号,则与当前符号栈顶符号比较,如果符号栈顶符号优先级大于等于当前符号,则弹出栈顶符号以及两个数字进行运算,结果压回数字栈
4、最后,对符号栈、数字栈中残留的运算进行操作,直到符号栈为空
5、栈顶元素即为结果
注意:每一步运算、最后输出结果都需要对10000取模。
100分代码:
#include <bits/stdc++.h>
using namespace std;
string str;
stack<char> os; //符号栈
stack<long long> ns; //数字栈
unordered_map<char, int> prior = {{'+', 1}, {'*', 2}};
void eval()
{
int res;
char op = os.top(); os.pop();
int a = ns.top(); ns.pop();
int b = ns.top(); ns.pop();
if(op == '+') res = (a + b) % 10000;
if(op == '*') res = (a % 10000) * (b % 10000) % 10000;
ns.push(res);
}
int main()
{
cin >> str;
int num = 0;
for(int i = 0; i < str.length(); i++)
{
if(str[i] >= '0' && str[i] <= '9') //遇到数字,提取整数入数字栈
{
long long num = 0;
int j = i;
while(str[j] >= '0' && str[j] <= '9' && j < str.length())
{
num = num * 10 + str[j] - '0';
j++;
}
ns.push(num);
i = j - 1;
}
else //遇到符号,看符号栈顶符号优先级是否大于等于当前符号,是则对前面的符号和数字进行运算
{
if(os.size() && prior[os.top()] >= prior[str[i]])
{
eval();
}
os.push(str[i]);
}
}
while(os.size()) eval();
cout << ns.top() % 10000; //主要最后也要%10000,因为表达式可能只有一个数超过4位
return 0;
}
标签:NOIP2013,P1981,符号,int,str,求值,10000,ns,os From: https://www.cnblogs.com/jcwy/p/18226488