#include<stdio.h>
#define MAXSIZE 30
typedef int Status;
typedef struct Stack_
{
Status s[MAXSIZE];
int top;
}Stack,*StackPtr;
void StackInit(StackPtr stk);
void Push(StackPtr stk,Status t);
void Pop(StackPtr stk);
Status GetStackTop(StackPtr stk);
void Translation(StackPtr stk,char str[]);//把中缀表达式转化为后缀表达式存储在栈中
void Claclulation(StackPtr stk);//计算后缀表达式

int main(void)
{
Stack stk;//stk栈用来存储后缀表达式
char s[30];//输入中缀表达式
printf("请输入表达式：");
scanf("%s",s);
Translation(&stk,s);
Claclulation(&stk);
return 0;
}

void StackInit(StackPtr stk)
{
stk->top=-1;
}

void Push(StackPtr stk,Status t)
{
stk->top++;
stk->s[stk->top]=t;
}

void Pop(StackPtr stk)
{
stk->top--;
}

Status GetStackTop(StackPtr stk)
{
return stk->s[stk->top];
}

void Translation(StackPtr stk,char str[])
{
StackInit(stk);
Stack symbolStack;//转换过程中用到符号栈
StackPtr symbol=&symbolStack;
StackInit(symbol);
int i=0;//str的下标
char ch;
while((ch=str[i++])!=‘\0‘)
{
if(ch>=‘0‘&&ch<=‘9‘)
{
Push(stk,ch);
while((ch=str[i++])!=‘\0‘&&ch>=‘0‘&&ch<=‘9‘)
Push(stk,ch);
Push(stk,‘ ‘);
i--;//最后次while循环多加了一次i
}
else if(ch==‘+‘||ch==‘-‘)
{
while(symbol->top!=-1&&symbol->s[symbol->top]!=‘(‘)
{
Push(stk,symbol->s[symbol->top]);
Pop(symbol);
}
Push(symbol,ch);
}
else if(ch==‘*‘||ch==‘/‘)
{
while(symbol->s[symbol->top]!=‘(‘&&(symbol->s[symbol->top]==‘*‘||symbol->s[symbol->top]==‘/‘))
{
Push(stk,symbol->s[symbol->top]);
Pop(symbol);
}
Push(symbol,ch);
}
else if(ch==‘(‘)
{
Push(symbol,ch);
}
else if(ch==‘)‘)
{
while(GetStackTop(symbol)!=‘(‘)
{
Push(stk,GetStackTop(symbol));
Pop(symbol);
}
Pop(symbol);//‘(‘出栈
}

}

while(symbol->top!=-1)
{
Push(stk,GetStackTop(symbol));
Pop(symbol);
}

Push(stk,‘\0‘);
int j=0;
while(stk->s[j]!=‘\0‘)
printf("%c",stk->s[j++]);
printf("\n");
}

void Claclulation(StackPtr stk)
{
Stack num;
StackPtr numPtr=&num;
StackInit(numPtr);//定义一个数字栈
int result;
int k=0;
while(stk->s[k]!=‘\0‘)
{
if(stk->s[k]>=‘0‘&&stk->s[k]<=‘9‘)
{
int add=0;
while(stk->s[k]!=‘ ‘)
{
add=10*add+(stk->s[k++]-‘0‘);
}
Push(numPtr,add);
}
else if(stk->s[k]==‘+‘||stk->s[k]==‘-‘||stk->s[k]==‘*‘||stk->s[k]==‘/‘)
{
switch(stk->s[k])
{
case ‘+‘:
{
int c1=GetStackTop(numPtr);
Pop(numPtr);
int c2=GetStackTop(numPtr);
Pop(numPtr);
result=c1+c2;
Push(numPtr,result);
break;
}

case ‘-‘:
{
int c1=GetStackTop(numPtr);
Pop(numPtr);
int c2=GetStackTop(numPtr);
Pop(numPtr);
result=c2-c1;
Push(numPtr,result);
break;
}

case ‘*‘:
{
int c1=GetStackTop(numPtr);
Pop(numPtr);
int c2=GetStackTop(numPtr);
Pop(numPtr);
result=c1*c2;
Push(numPtr,result);
break;
}

case ‘/‘:
{
int c1=GetStackTop(numPtr);
Pop(numPtr);
int c2=GetStackTop(numPtr);
Pop(numPtr);
result=c2/c1;
Push(numPtr,result);
break;
}

}//switch

}//if
k++;
} //while

printf("%d",result);
}

表达式求值