c语言中缀后缀算术表达式求值用栈实现

c语言 中缀、后缀 算术表达式求值用栈实现

#include<stdio.h>

#include<string.h>

#include<malloc.h>

#include<stdlib.h>

#define MaxSize 50

typedef struct

{

float data[MaxSize];

int top;

}OpStack;

typedef struct

{

char data[MaxSize];

int top;

}SeqStack;

void InitStack(SeqStack *S);//初始化栈

int StackEmpty(SeqStack S);//判断栈是否为空

int PushStack(SeqStack *S,char e);//进栈

int PopStack(SeqStack *S,char *e);//删除栈顶元素

int GetTop(SeqStack S,char *e);//取栈顶元素

void TranslateExpress(char s1[],char s2[]);//将中缀表达式转化为后缀表达式

float ComputeExpress(char s[]);//计算后缀表达式的值

void main()

{

char a[MaxSize],b[MaxSize];

float f;

printf("请输入一个算术表达式:\\n");

gets(a);

printf("中缀表达式为：%s\\n",a);

TranslateExpress(a,b);

printf("后缀表达式为：%s\\n",b);

f=ComputeExpress(b);

printf("计算结果：%f\\n",f);

}

void InitStack(SeqStack *S)//初始化栈

{

S->top=0;

}

int StackEmpty(SeqStack S)//判断栈是否为空

{

if(S.top ==0)

return 1;

else

return 0;

}

int PushStack(SeqStack *S,char e)//进栈

{

if(S->top>=MaxSize)

{

printf("栈已满，不能进栈!");

return 0;

}

else

{

S->data[S->top]=e;

S->top++;

return 1;

}

}

int PopStack(SeqStack *S,char *e)//删除栈顶元素

{

if(S->top==0)

{

printf("栈已空\\n");

return 0;

}

else

{

S->top--;

*e=S->data[S->top];

return 1;

}

}

int GetTop(SeqStack S,char *e)//取栈顶元素

{

if(S.top<=0)

{

printf("栈已空");

return 0;

}

else

{

*e=S.data[S.top-1];

return 1;

}

}

void TranslateExpress(char str[],char exp[])//把中缀表达式转换为后缀表达式

{

SeqStack S;

char ch;

char e;

int i=0,j=0;

InitStack(&S);

ch=str[i];

i++;

while(ch!='\\0') {

switch(ch)

{

case'(':

PushStack(&S,ch);

//依次扫描中缀表达式

break;

case')':

while(GetTop(S,&e)&&e!='(')

{

PopStack(&S,&e);

exp[j]=e;

j++;

}

PopStack(&S,&e);

break;

case'+':

case'-':

while(!StackEmpty(S)&&GetTop(S,&e)&&e!='(')

{

PopStack(&S,&e);

exp[j]=e;

j++;

}

PushStack(&S,ch);

break;

case'*':

case'/':

while(!StackEmpty(S)&&GetTop(S,&e)&&e=='/'||e=='*')

{

PopStack(&S,&e);

exp[j]=e;

j++;

}

PushStack(&S,ch);

break; //是空格就忽略

case' ':

break;

default:

while(ch>='0'&&ch<='9')

{

exp[j]=ch;

j++;

ch=str[i];

i++;

}

i--;

exp[j]=' ';

j++;

}

ch=str[i];

i++;

}

while(!StackEmpty(S)) //将栈中剩余运算符出栈

{

PopStack(&S,&e);

exp[j]=e;

j++;

}

exp[j]='\\0';

}

float ComputeExpress(char a[])//计算后缀表达式的值

{

OpStack S;

int i=0;

float x1,x2,value;

float result;

S.top=-1;

while(a[i]!='\\0') //依次扫描后缀表达式

{

if(a[i]!='

'&&a[i]>='0'&&a[i]<='9')//

如果

是数字

{

value=0;

while(a[i]!=' ') //如果不是空格

{

value=10*value+a[i]-'0';

i++;

}

S.top++;

S.data[S.top]=value; //处理后进栈

}

else //如果是运算符

{

switch(a[i])

{

case'+':

x1=S.data[S.top];

S.top--;

x2=S.data[S.top];

S.top--;

result=x1+x2;

S.top++;

S.data[S.top]=result;

break;

case'-':

x1=S.data[S.top];

S.top--;

x2=S.data[S.top];

S.top--;

result=x2-x1;

S.top++;

S.data[S.top]=result;

break;

case'*':

x1=S.data[S.top];

S.top--;

x2=S.data[S.top];

S.top--;

result=x1*x2;

S.top++;

S.data[S.top]=result;

break;

case'/':

x1=S.data[S.top];

S.top--;

x2=S.data[S.top];

S.top--;

result=x2/x1;

S.top++;

S.data[S.top]=result;

break;

}

i++;

}

}

if(!S.top!=-1) //如果栈不空，将结果出栈并返回

{

result=S.data[S.top];

S.top--;

if(S.top==-1)

return result;

else

{

printf("表达式错误");

exit(-1);

}

}

return 0;

}