当前位置:网站首页>acwing 3302. 表达式求值
acwing 3302. 表达式求值
2022-07-04 19:13:00 【_刘小雨】
给定一个表达式,其中运算符仅包含 +,-,*,/(加 减 乘 整除),可能包含括号,请你求出表达式的最终值。
注意:
数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现,不会作为负号出现,例如,-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
题目保证表达式中所有数字均为正整数。
题目保证表达式在中间计算过程以及结果中,均不超过 231−1。
题目中的整除是指向 0 取整,也就是说对于大于 0 的结果向下取整,例如 5/3=1,对于小于 0 的结果向上取整,例如 5/(1−4)=−1。
C++和Java中的整除默认是向零取整;Python中的整除//默认向下取整,因此Python的eval()函数中的整除也是向下取整,在本题中不能直接使用。
输入格式
共一行,为给定表达式。
输出格式
共一行,为表达式的结果。
数据范围
表达式的长度不超过 105。
输入样例:
(2+2)*(1+1)
输出样例:
8
关键:
需要用两个栈, 一个栈用于保存数字,另一个需要保存操作运算符
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int> num; // 保存数字栈
stack<char> op; // 保存运算符栈
void eval()
{
auto b = num.top(); num.pop(); // 取数字
auto a = num.top(); num.pop(); // 取数字
auto 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}}; // 如果有^, 可以直接在后面加 {'^',3}
string str;
cin >> str;
for (int i = 0; i < str.size(); i ++ )
{
auto 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() && op.top() != '(' && pr[op.top()] >= pr[c]) eval(); // 栈里面保存的优先级 >= 当前的优先级
op.push(c);
}
}
while (op.size()) eval();
cout << num.top() << endl;
return 0;
}
边栏推荐
- 被奉为经典的「金字塔原理」,教给我们哪些PPT写作技巧?
- 九齐NY8B062D MCU规格书/datasheet
- 奏响青春的乐章
- FS4061A升压8.4V充电IC芯片和FS4061B升压12.6V充电IC芯片规格书datasheet
- MySQL statement execution details
- B2B mall system development of electronic components: an example of enabling enterprises to build standardized purchase, sale and inventory processes
- [today in history] July 4: the first e-book came out; The inventor of magnetic stripe card was born; Palm computer pioneer was born
- 左右最值最大差问题
- Flet tutorial 05 outlinedbutton basic introduction (tutorial includes source code)
- 2022 version of stronger jsonpath compatibility and performance test (snack3, fastjson2, jayway.jsonpath)
猜你喜欢
Flet教程之 06 TextButton基础入门(教程含源码)
电脑共享打印机拒绝访问要怎么办
Flet教程之 04 FilledTonalButton基础入门(教程含源码)
AP8022开关电源小家电ACDC芯片离线式开关电源IC
[Beijing Xunwei] i.mx6ull development board porting Debian file system
What should I do if my computer sharing printer refuses access
Win11怎么搜索无线显示器?Win11查找无线显示器设备的方法
[in-depth learning] review pytoch's 19 loss functions
Win11U盘拒绝访问怎么办?Win11U盘拒绝访问的有效解决方法
九齐NY8B062D MCU规格书/datasheet
随机推荐
Browser render page pass
Redis分布式锁的实现
【历史上的今天】7 月 4 日:第一本电子书问世;磁条卡的发明者出生;掌上电脑先驱诞生
See how Tencent does interface automation testing
#夏日挑战赛#带你玩转HarmonyOS多端钢琴演奏
In operation (i.e. included in) usage of SSRs filter
Win11U盘拒绝访问怎么办?Win11U盘拒绝访问的有效解决方法
阿里测试师用UI自动化测试实现元素定位
六石编程学:关于代码,有六个得意
同事的接口文档我每次看着就头大,毛病多多。。。
C # better operation mongodb database
什么叫内卷?
go语言笔记(4)go常用管理命令
为什么最大速度是光速
哈希(Hash)竞猜游戏系统开发功能分析及源码
Form组件常用校验规则-1(持续更新中~)
Ziguang zhanrui completed the first 5g R17 IOT NTN satellite on the Internet of things in the world
MySQL statement execution details
【ISMB2022教程】图表示学习的精准医疗,哈佛大学Marinka Zitnik主讲,附87页ppt
漫谈客户端存储技术之Cookie篇