STL-stack栈：P1981 [NOIP2013 普及组] 表达式求值

这个题用的STL-栈来做
题目来源：洛谷
相关知识

[NOIP2013 普及组] 表达式求值

题目背景

NOIP2013 普及组 T2

题目描述

给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

输入格式

一行，为需要你计算的表达式，表达式中只包含数字、加法运算符 + 和乘法运算符 *，且没有括号，所有参与运算的数字均为 $0$ 到 $2^{31}-1$ 之间的整数。

输入数据保证这一行只有 0123456789+* 这 $12$ 种字符。

输出格式

一个整数，表示这个表达式的值。

注意：当答案长度多于 $4$ 位时，请只输出最后 $ 4$ 位，前导 $ 0$ 不输出。

样例 #1

样例输入 #1

1+1*3+4

样例输出 #1

8

样例 #2

样例输入 #2

1+1234567890*1

样例输出 #2

7891

样例 #3

样例输入 #3

1+1000000003*1

样例输出 #3

4

提示

对于 $30\%$ 的数据，$0\le$ 表达式中加法运算符和乘法运算符的总数 $\le 100$。

对于 $80\%$ 的数据，$0\le$ 表达式中加法运算符和乘法运算符的总数 $\le 1000$。

对于 $100\%$ 的数据，$0\le$ 表达式中加法运算符和乘法运算符的总数 $\le 100000$。

题意

求出一个只含*和+的表达式的值（中缀表达式），但是值只输出后四位（去除前导0）

思路

• 题目因为只有*和+就相对简单。表达式求值可以用栈来做，字符串储存数据然后分别压入栈处理。但因为某个数字是字符串如：12345 ，所以需要特殊处理，遇到下一个符号/换行符时，才会得到该数据

     if (isdigit(c)) {num = num * 10 + (c - '0'); isdigit(c) 计算机C(C++)语言中的一个函数，主要用于检查其参数是否为十进制数字字符。}
  

• 只有两个运算符，因为考虑优先级，所以符号就没必要压入栈，只需要即将运算的数据放入栈中，每次遇到符号后就处理：计算当前表达式a +/* b ，将结果压入栈即可。但什么时候压栈？什么时候出栈？

• 可以考虑栈中只存放所有相加的数据，即：将优先级高的 *先计算出来！

  如： k+a*b+c

  • a*b的结果要当遍历到b时，才会计算结果，而要确定b这个数据（像12345 这个数字，就是字符串遍历到5之后如果出现了字符’+'才会确定），就需要遇到下一个符号时才会计算，即：考虑用变量储存b之前的符号，当遍历完b后，把计算a*b的相乘的结果，并储存当前运算符。
    

• 题目要求只输出最后四位，我们只需要将每一个压入栈的数据%10000即可！注意是四个0！。而前导0 的问题，由于计算都是用int类型，%10000后会自动去掉无效的前导0

数据约束

暂无
参考代码

#include <bits/stdc++.h>
using namespace std;
int m = 10000; 
int main() {string a;getline(cin, a);  // 读取表达式stack<int> s;  // 栈用于存储数值int num = 0;  // 临时存储当前数字char op = '+';  // 当前操作符，初始化为加号for (int i = 0; i < a.size(); i++) {char c = a[i];// 如果是数字 isdigit(c) 计算机C(C++)语言中的一个函数，主要用于检查其参数是否为十进制数字字符。if (isdigit(c)) {num = num * 10 + (c - '0');}// 如果是运算符或者是最后一个字符if (!isdigit(c)|| i == a.size() - 1) {if (op == '+') {s.push(num%m);  // 当前是加法，直接入栈} else if (op == '*') {int top = s.top();s.pop();s.push((top * num)%m);  // 当前是乘法，和栈顶数值进行乘法运算} op = c;  // 更新操作符num = 0;  // 重置当前数字}}// 计算结果int result = 0;while (!s.empty()) {result += s.top();result %= m;s.pop();}cout << result;  // 输出计算结果return 0;
}