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

雨点打透心脏的1/2处 2022-06-11 09:22 175阅读 0赞

###     ###

若已经给出了后缀式，求值，其规则为，建立一个栈，从左到右计算。若为数值，入栈，若为运算符，让栈顶两个数值运算，且运算顺序为从左到右，并把新的元素重新入栈。此题用数组也可解决，

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

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

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

#### Input ####

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

#### Output ####

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

#### Example Input ####

59*684/-3*+#

#### Example Output ####

#### Hint ####

基本操作数都是一位正整数!

代码：

\#include <stdio.h>  
\#include <stdlib.h>  
\#include <string.h>  
\#define STACKINCREMENT 10000 //存储空间分配增量  
\#define STACKINITSIZE 10000 //存储空间初始分配量  
typedef int SElemType;  
typedef struct  
\{  
SElemType \*base;//定义栈底指针；  
SElemType \*top;//定义暂定指针，  
int stacksize;//当前已分配的存储空间  
\}SqStack;  
int InitStack(SqStack \*S) //初始化栈  
\{  
S->base = (SElemType \*)malloc(STACKINITSIZE\*sizeof(SElemType));//为栈底开辟空间  
if(!S->base)  
return 0;//如果开辟空间失败，返回为0；  
S->top= S->base;  
S->stacksize = STACKINITSIZE;//S->stacksize为开辟的空间  
return 1;  
\}  
int Push(SqStack \*S,int e)//入栈函数  
\{  
if(S->top - S->base>=S->stacksize)//先判断空间是否足够  
\{  
S->base = (SElemType \*)realloc(S->base, (S->stacksize + STACKINCREMENT)\*sizeof(SElemType));//新开的空间，用realloc函数  
if(!S->base)  
return 0;//如果创建失败，返回0  
S->top = S->base + S->stacksize;//再次确定S->top的地址，防止S->base改变。而丢失了S->top的地址  
S->stacksize = S->stacksize + STACKINCREMENT;//更新S->stacksize  
\}  
\*(S->top) = e;//进行进栈操作  
S->top++;  
return 1;  
\}  
  
  
  
  
int f(char a,int b,int c)  
\{  
if(a=='+')  
return b+c;  
if(a=='-')  
return b-c;  
if(a=='\*')  
return b\*c;  
if(a=='/')  
return b/c;  
return 1;  
\}  
int Judge(char s,SqStack \*S)  
\{  
int t;  
t = f(s,\*(S->top-2),\*(S->top-1));//前一个与后一个运算，一定要搞清楚运算顺序，搞明白哪两个进行运算。  
S->top--;  
\*(S->top-1) = t;  
return 1;  
\}  
int main()  
\{  
SqStack S;  
InitStack(&S);  
char s\[10000\];  
gets(s);  
int n = strlen(s);  
int i;  
for(i = 0;i<=n-1;i++)  
\{  
if(s\[i\]=='\#')  
break;  
if(s\[i\]>='0'&&s\[i\]<='9')  
\{  
Push(&S,(int)(s\[i\]-48));//将char型转成数值型，直接相减也行，直接为数值型，‘s\[i\] ’-'0',也可以  
  
  
\}  
else if(s\[i\]=='+'||s\[i\]=='-'||s\[i\]=='\*'||s\[i\]=='/')  
\{  
Judge(s\[i\],&S);  
\}  
\}  
printf("%d",\*(S.top-1));//最后输出栈顶元素  
  
  
printf("\\n");  
  
  
return 0;  
\}

法二：数组。

[view source][]

[print][] [?][Link 1]

<table style="border-spacing:0px; border-collapse:collapse!important; background:none!important; margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:auto!important"> 
 <tbody style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; background:none!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:auto!important"> 
  <tr style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; background:none!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:auto!important"> 
   <td style="padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; background:none!important; float:none!important; vertical-align:top!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:3em!important; line-height:1.1em!important; font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; font-size:1em!important; min-height:auto!important; color:rgb(175,175,175)!important"> <code style="color:rgb(199,37,78); font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; font-size:1em!important; padding:0px 0.3em 0px 0px!important; background:none!important; margin:0px!important; border:0px!important; outline:0px!important; text-align:right!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:2.7em!important; line-height:1.1em!important; min-height:auto!important; display:block!important">16</code></td> 
   <td style="padding:0px 0px 0px 0.5em!important; margin:0px!important; border-width:0px 0px 0px 3px!important; border-top-style:initial!important; border-right-style:initial!important; border-bottom-style:initial!important; border-left-style:solid!important; border-top-color:initial!important; border-right-color:initial!important; border-bottom-color:initial!important; border-left-color:rgb(108,226,108)!important; outline:0px!important; background:none!important; float:none!important; vertical-align:top!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; font-size:1em!important; min-height:auto!important"> <code style="font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; font-size:1em!important; padding:0px!important; color:rgb(128,128,128)!important; background:none!important; font-weight:bold!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:auto!important">int</code>&nbsp;<code style="font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; font-size:1em!important; padding:0px!important; background:none!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:auto!important">Judge(</code><code style="font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; font-size:1em!important; padding:0px!important; color:rgb(128,128,128)!important; background:none!important; font-weight:bold!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:auto!important">char</code>&nbsp;<code style="font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; font-size:1em!important; padding:0px!important; background:none!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:auto!important">s,</code><code style="font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; font-size:1em!important; padding:0px!important; color:rgb(128,128,128)!important; background:none!important; font-weight:bold!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:auto!important">int</code>&nbsp;<code style="font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; font-size:1em!important; padding:0px!important; background:none!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:auto!important">a[],</code><code style="font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; font-size:1em!important; padding:0px!important; color:rgb(128,128,128)!important; background:none!important; font-weight:bold!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:auto!important">int</code>&nbsp;<code style="font-family:Consolas,&quot;Bitstream Vera Sans Mono&quot;,&quot;Courier New&quot;,Courier,monospace!important; font-size:1em!important; padding:0px!important; background:none!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:auto!important">n)</code></td> 
  </tr> 
 </tbody> 
</table>

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2208/pid/2133.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2208/pid/2133.html
[view source]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Viewcode/view/sid/2707825#viewSource
[print]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Viewcode/view/sid/2707825#printSource
[Link 1]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Viewcode/view/sid/2707825#about