題目描述

對于一個基于二元運算符的后綴表示式（基本操作數都是一位正整數），求其代表的算術表達式的值。

輸入

輸入一個算術表達式的后綴式字符串，以‘#’作為結束標志。

輸出

求該后綴式所對應的算術表達式的值，并輸出之。

示例輸入

59*684/-3*+#

示例輸出

57

#include <stdio.h>
#include<stdlib.h>
#define maxstack 1000
#define stacknum 1000
typedef struct
{
? ? int *top,*base;
? ? int stacksize;
}stack;
void Initstack(stack &s)//棧的初始化；
{
? ? s.base=(int *)malloc(maxstack*sizeof(int));
? ? if(!s.base) exit(0);//棧溢出；
? ? s.top=s.base;
? ? s.stacksize=maxstack;
}
void push(stack &s,char e)//進棧；
{
? ? if(s.top-s.base>=s.stacksize)
? ? {
? ? ? ? s.base=(int *)realloc(s.base,(maxstack+stacknum)*sizeof(int));
? ? ? ? if(!s.base) exit(0);//棧溢出；
? ? ? ? s.top=s.base+s.stacksize;
? ? ? ? s.stacksize+=stacknum;
? ? }
? ? s.top++;//棧頂元素為e；
? ? *s.top=e;
}
int Empty(stack &s)//判斷是否為空棧；
{
? ? if(s.base==s.top)
? ? ? ? return 1;
? ? ? ? return 0;


}
void Pop(stack &s)//出棧；
{
? ? if(!Empty(s))
? ? ? ? s.top--;


}
void print(stack &s)
{//、棧內元素的輸出；
? ? while(s.top!=s.base)
? ? {
? ? ? ? printf("%c",*s.top);
? ? ? ? Pop(s);
? ? }
? ? printf("\n");
}
void cal(stack &s,char st[],int n)//由棧的后綴式求值
{
? ? int i,pr,la;
? ? int ch;
? ? for(i=1;i<=n;i++)
? ? {
? ? ? ? if(st[i]>='1'&&st[i]<='9')//數字進棧；
? ? ? ? {
? ? ? ? ? ? ch=(st[i]-'0');
? ? ? ? ? ? push(s,ch);
? ? ? ? }
? ? ? ? else if(st[i]=='+')//+號棧內兩個數出棧計算再進棧；
? ? ? ? {
? ? ? ? ? ? pr=*s.top;
? ? ? ? ? ? s.top--;
? ? ? ? ? ? la=*s.top;
? ? ? ? ? ? *s.top=pr+la;
? ? ? ? }
? ? ? ? else if(st[i]=='*')
? ? ? ? {
? ? ? ? ? ? pr=*s.top;
? ? ? ? ? ? s.top--;
? ? ? ? ? ? la=*s.top;
? ? ? ? ? ? *s.top=pr*la;
? ? ? ? }
? ? ? ? else if(st[i]=='-')
? ? ? ? {
? ? ? ? ? ? pr=*s.top;
? ? ? ? ? ? s.top--;
? ? ? ? ? ? la=*s.top;
? ? ? ? ? ? *s.top=la-pr;
? ? ? ? }
? ? ? ? else if(st[i]=='/')
? ? ? ? {
? ? ? ? ? ? pr=*s.top;
? ? ? ? ? ? s.top--;
? ? ? ? ? ? la=*s.top;
? ? ? ? ? ? *s.top=la/pr;
? ? ? ? }
? ? }
? ? printf("%d\n",*s.top);
}
int main()
{
? ? char ch,st[10000];
? ? int i=0;
? ? stack s;//棧的定義
? ? Initstack(s);//棧的初始化；
? ? while(~scanf("%c",&ch))
? ? {
? ? ? ? if(ch!='#')
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? ? ? ? st[i]=ch;
? ? ? ? ? ? }
? ? ? ? ?else
? ? ? ? ? ? ? ? break;
? ? }
? ? cal(s,st,i);
? ? return 0;
}

總結

以上是生活随笔為你收集整理的数据结构实验之栈三：后缀式求值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。