数据结构实验之栈三：后缀式求值

数据结构实验之栈三：后缀式求值

Time Limit: 1000MS  Memory Limit: 65536KB Submit  Statistic

Problem Description

对于一个基于二元运算符的后缀表示式（基本操作数都是一位正整数），求其代表的算术表达式的值。

Input

输入一个算术表达式的后缀式字符串，以‘#’作为结束标志。

Output

求该后缀式所对应的算术表达式的值，并输出之。

Example Input

59*684/-3*+#

Example Output

57 思路就是用栈来存储数，每次遇到运算符从栈顶拿出两个数字运算完之后，新的数重新压入栈。

#include <iostream> #include <bits/stdc++.h> using namespace std; const int MAXN=10000+5; char s[MAXN]; int st[MAXN]; int get_value(int x,int y,char s) { if(s=='+')return x+y; if(s=='-')return x-y; if(s=='*')return x*y; return x/y; } int main() { int top=0; scanf("%s",s); int i=0; while(s[i]!='#') { if(isdigit(s[i]))st[top++]=s[i]-'0'; else { int x=st[--top]; int y=st[--top]; st[top++]=get_value(y,x,s[i]); } i++; } printf("%d\n",st[0]); return 0; } /*************************************************** Result: Accepted Take time: 0ms Take Memory: 164KB Submit time: 2016-09-19 10:57:21 ****************************************************/