#include<stdio.h>

#include<math.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=='-')

{

if(symbol->top!=-1&&symbol->s[symbol->top]!='(')//当输入'('，没有遇到')'时不能Pop

{

Push(stk,symbol->s[symbol->top]);

Pop(symbol);

}

Push(symbol,ch);

}

else if(ch=='*'||ch=='/'||ch=='%')

{

if(symbol->s[symbol->top]!='('&&(symbol->s[symbol->top]=='^'||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=='^')

{

if(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]=='/'||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;

}

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=(int)pow(c2,c1);

Push(numPtr,result);

break;

}

}//switch

}//if

k++;

} //while

printf("%d\n",result);

}