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; }

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; }

本文来源：https://www.bwwdw.com/article/sv2v.html