求后缀表达式的值

后缀表达式的值

【题目描述】

从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。

比如，16–9*(4+3)转换成后缀表达式为：16□9□4□3□+*–，在字符数组A中的形式为：

栈中的变化情况：

运行结果：-47

提示：输入字符串长度小于250，参与运算的整数及结果之绝对值均在2^64范围内，如有除法保证能整除。

【输入】

一个后缀表达式。

【输出】

一个后缀表达式的值。

【输入样例】

16 9 4 3 +*-@

【输出样例】

-47

 如果你还没有学习过栈这种数据结构，那这道题目将有点困难。

什么是后缀表达式

后缀式即逆波兰式，当计算机要计算一个表达式时，计算机不像人，能够直接看出各符号的优先级，对优先级高的先进行计算，所以需要后缀表达式来使计算机也能看懂并且计算表达式。

不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：16 9 4 3 +*-  

 4 + 3 = 7 

7 * 9 = 64

16 - 64 = -47

思路

一、先将字符串读入，中间有空格，普通的输入方式不行，要么输入一行要么直到回车才停止输入

二、遍历整个字符串，考虑会遇到哪些情形，会遇到加减乘除、数字、空格，如果是空格就跳过，是数字就入栈，是运算符就将栈顶和栈顶后面一个元素进行运算（注意顺序），然后将这两个元素出栈，再将运算的结果入栈

三、遇到 ' @ ' 就停止遍历

题解

#include <iostream>
#include <string>using namespace std;//数组模拟栈
long long stk[250]; //题目中说明了数据范围在2^64内，故用long long
int tt;int main(void)
{/*char arr[250];scanf("%[^\n]s", arr); // 输入一行，直到遇到\n*/// 或者可以这样写string arr;getline(cin, arr);long long temp = 0;for (int i = 0; arr[i] != '@'; i++ ){if (arr[i] == '+'){temp = stk[tt - 1] + stk[tt ];tt--; tt--;stk[++tt] = temp;//这几步可以简化 例如// stk [tt -1 ] = stk [tt -1 ] + stk [tt] ;// tt --;}else if (arr[i] == '-'){temp = stk[tt - 1] - stk[tt ]; // 注意前后顺序tt--; tt--;stk[++tt] = temp;}else if (arr[i] == '*'){temp = stk[tt] * stk[tt - 1];tt--; tt--;stk[++tt] = temp;}else if (arr[i] == '/'){temp = stk[tt - 1] / stk[tt ];tt--; tt--;stk[++tt] = temp;}else if (arr[i] == ' '){;}else{temp = 0; //入栈的数可能是多位数while (arr[i] != ' '){temp = temp * 10 + (arr[i] - '0');i++;}stk[++tt] = temp;}}printf("%lld\n", stk[tt]);return 0;
}