PDF文档公众号回复关键字:20241001
1 P1449 后缀表达式
[题目描述]
所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）
本题中运算符仅包含 + - * / 。保证对于 / 运算除数不为 0。特别地，其中 /运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。
如：3(5-2)+7 对应的后缀表达式为：3.5.2.-7.+@ 。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号
[输入格式]
输入一行一个字符串 ss，表示后缀表达式
[输出格式]
输出一个整数，表示表达式的值
[输入输出样例]
输入 #1
3.5.2.-*7.+@
输出 #1
16
输入 #2
10.28.30./*7.-@
输出 #2
-7
说明/提示
数据保证，1≤∣s∣≤50，答案和计算过程中的每一个值的绝对值不超过 10^9
2 相关知识点
1) 栈
栈又名堆栈，是一种限定仅在表尾进行插入和删除操作的线性表，这一端称为栈顶，另一端称为栈底
栈中的数据元素遵守后进先出的原则
2) 字符读取
getchar读取字符
#include<bits/stdc++.h>
using namespace std;
char c;//定义字符c
int main(){
while(c!='\n'){//不是换行 继续读下一个字符
c=getchar();//读取1个字符 赋值给c变量
cout<<c<<" ";//输出
}
return 0;
}
/*
输入
12345
输出
1 2 3 4 5
*/
3) 后缀表达式
后缀表达式，也称为逆波兰表达式，是一种算术表达式表示方法，其中运算符位于操作数之后
//示例1 中缀表达式a+b对应的后缀表达式C++
a b+
//示例2 中缀表达式3+4*2对应的前缀表达式
3 4 2 * +
3 思路分析
1依次读入 3 5 2这3个操作数
2 读入操作符 - 此时从栈中读入栈顶的2个元素，y和x
对y和x进行计算后的结果放入栈中
x-y=5-2=3
3 读入操作符 * 此时从栈中读入栈顶的2个元素，y和x
对y和x进行计算后的结果放入栈中
x*y=3*3=9
4 读入操作符 + 此时从栈中读入栈顶的2个元素，y和x
对y和x进行计算后的结果放入栈中
x+y=9+7=16
此时栈顶元素就是此后缀表达式的计算结果
示例程序
#include<bits/stdc++.h>
using namespace std;
stack<int> st;//栈 用来保存操作数
//sum 保存操作数 每次读取1个字符，有可能多位
int sum,x,y;//x和y临时保存从栈中取出的2个数
char c;//每次读取一个字符
int main(){
while(c!='@'){//如果字符不是@ 说明没结束
c=getchar();//读取1个字符
if(c=='+'){//如果是+
y=st.top();//从栈中取出栈顶第1个数
st.pop();//从栈中弹出
x=st.top();//从栈中取出栈顶第2个数
st.pop();//从栈中弹出
st.push(x+y);//2个数的和存入栈中
}else if(c=='-'){//如果是-
y=st.top();//从栈中取出栈顶第1个数
st.pop();//从栈中弹出
x=st.top();//从栈中取出栈顶第2个数
st.pop();//从栈中弹出
st.push(x-y);//第2个数-第1个数存入栈中
}else if(c=='*'){//如果是*
y=st.top();//从栈中取出栈顶第1个数
st.pop();//从栈中弹出
x=st.top();//从栈中取出栈顶第2个数
st.pop();//从栈中弹出
st.push(x*y);//两个数乘积放入栈中
}else if(c=='/'){//如果是 /
y=st.top();//从栈中取出栈顶第1个数
st.pop();//从栈中弹出
x=st.top();//从栈中取出栈顶第2个数
st.pop();//从栈中弹出
st.push(x/y);//第2个数/第1个数存入栈中
}else if(c=='.'){//如果是. 说明操作数读取结束 操作数sum放入栈中
st.push(sum);
sum=0;//清除m 继续读下一个操作数
}else{
sum=sum*10+c-'0';//按位累加操作数
}
}
cout<<st.top();//此时栈顶元素就计算结果
return 0;
}