当前位置：首页 > web >正文

【数据结构入门训练DAY-18】信息学奥赛一本通T1331-后缀表达式的值

web 2025/7/17 6:52:29

文章目录

前言
一、题目
二、解题思路
总结

前言

本次训练内容：

栈的复习。
栈模拟四则运算计算问题的练习。
训练解题思维。

一、题目

从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。比如，16–9*(4+3)转换成后缀表达式为：16□9□4□3□+*–，运行结果：-47。提示：输入字符串长度小于250，参与运算的整数及结果之绝对值均在2^64范围内，如有除法保证能整除。

输入格式

一个后缀表达式。

输出格式

一个后缀表达式的值。

样例输入

16 9 4 3 +*-@

样例输出

-47

二、解题思路

这道题目是让我们把字符串中的数字存入栈中，然后从后面的‘+-*/’的顺序依次进行计算,出现'@'是结束。我的思路是创建两个栈s，s1和对应的字符串，然后通过定义一个指针i去遍历字符串，把字符串中的数字元素存入s；每当遇到空格时，就先处理位数问题，位数处理就是定义两个变量作为指针给它初始值进行位运算，然后开始压入s1，每次操作一遍后要更新重置对应的两个指针。然后依次判断i指向的运算符是什么，并计算。

#include<bits/stdc++.h>
using namespace std;int main() {stack<char> s;stack<int>s1;//定义两个不同的栈int m=0,n=1;//定义位运算的变量作为指针int a,b;//定义指向运算时要出栈的两个元素的指针string str;getline(cin,str);for (auto i:str) {//智能指针法遍历if (i == '@') {//判断是否为结束符'@'break;}if (i>='0'&&i<='9') {//判断字符串的数字并存入s中s.push(i);}else if (i==' ') {//当到空格符时对栈中的元素进行位运算while (!s.empty()) {m=m+(s.top()-'0')*n;s.pop();n=n*10;}s1.push(m);//位运算结束后压入新栈m=0;n=1;}//对运算符进行对应的运算if (i == '+') {a=s1.top();s1.pop();b=s1.top();s1.pop();s1.push(a+b);}if (i == '-') {a=s1.top();s1.pop();b=s1.top();s1.pop();s1.push(b-a);}if (i == '*') {a=s1.top();s1.pop();b=s1.top();s1.pop();s1.push(a*b);}if (i == '/') {a=s1.top();s1.pop();b=s1.top();s1.pop();s1.push(b/a);}}cout<<s1.top()<<endl;//计算最终结果
}

因为题目的数据有正负和运算顺序的要求，所以需要保证进行减法和除法运算时，对应的变量位置书写正确。