#include<stdlib.h>
#define MaxOp 128
#define MaxSize 128
#define Size 128
struct //設定運算符優先級
{
char ch; //運算符
int pri; //優先級
}
lpri[]={{'=',0},{'(',1},{'*',5},{'/',5},{'+',3},{'-',3},{')',6}},
rpri[]={{'=',0},{'(',6},{'*',4},{'/',4},{'+',2},{'-',2},{')',1}};
int leftpri(char op) //求左運算符op的優先級
{
int i;
for(i=0;i<MaxOp;i++)
if(lpri[i].ch==op)
return lpri[i].pri;
}
int rightpri(char op) //求右運算符op的優先級
{
int i;
for(i=0;i<MaxOp;i++)
if(rpri[i].ch==op)
return rpri[i].pri;
}
int InOp(char ch) //判斷ch是否為運算符
{
if(ch=='('||ch==')'||ch=='+'||ch=='-'||ch=='*'||ch=='/')
return 1;
else
return 0;
}
int Precede(char op1,char op2) //op1和op2運算符優先級的比較結構
{
if(leftpri(op1)==rightpri(op2))
return 0;
else if(leftpri(op1)<rightpri(op2))
return -1;
else return 1;
}
void trans(char *exp,char postexp[])
//將算術表達式exp轉換為後綴表達式postexp
{
struct
{
char data[MaxSize]; //存放運算符
int top; //棧指針
}op; //定義運算符棧
int i=0; //i作為postexp的下標
op.top=-1;
op.top++; //將'='進棧
op.data[op.top]='=';
while(*exp!='\0') //exp表達式未掃描完時循環
{
if(!InOp(*exp)) //為數字字符的情況
{
while(*exp>='0'&&*exp<='9') //判定為數字
{
postexp[i++]=*exp;
exp++;
}
postexp[i++]='#'; //用#標誌壹個數值串的結束
}
else
switch(Precede(op.data[op.top],*exp))
{
case -1: //棧頂運算符的優先級低
op.top++;op.data[op.top]=*exp;
exp++; //繼續掃描其他字符
break;
case 0: // 只有括號滿足這種情況
op.top--; //將退棧
exp++;
break;
case 1:
postexp[i++]=op.data[op.top];
op.top--;
break;
}
}
while(op.data[op.top]!='=') //此時exp掃描完畢，退棧到'='為止
{
postexp[i++]=op.data[op.top];
op.top--;
}
postexp[i]='\0'; //給postexp表達式添加結束標誌
}
float compvalue(char *postexp) //計算後綴表達式postexp的值
{
struct
{
float data[MaxSize]; //存放數值
int top; //棧指針
}st;
float d,a,b,c;
st.top=-1;
while(*postexp!='\0') //postexp字符串未掃描完時循環
{
switch(*postexp)
{
case '+':
a=st.data[st.top];
st.top--;
b=st.data[st.top];
st.top--;
c=a+b;
st.top++;
st.data[st.top]=c;
break;
case '-':
a=st.data[st.top];
st.top--;
b=st.data[st.top];
st.top--;
c=b-a;
st.top++;
st.data[st.top]=c;
break;
case '*':
a=st.data[st.top];
st.top--;
b=st.data[st.top];
st.top--;
c=a*b;
st.top++;
st.data[st.top]=c;
break;
case '/':
a=st.data[st.top];
st.top--;
b=st.data[st.top];
st.top--;
if(a!=0)
{
c=b/a;
st.top++;
st.data[st.top]=c;
}
else
{
printf("\n\t除零錯誤！ \n");
exit(0);
}
break;
default:
d=0;
while(*postexp>='0'&&*postexp<='9')
{
d=10*d+*postexp-'0';
postexp++;
}
st.top++;
st.data[st.top]=d;
break;
}
postexp++;
}
return(st.data[st.top]);
}
void main()
{
for(;;)
{
char exp[Size];
char postexp[MaxSize];
printf("請輸入表達式:");
gets(exp);
trans(exp,postexp);
printf("中綴表達式: %s\n",exp);
printf("後綴表達式: %s\n",postexp);
printf("表達式的值: %g\n",compvalue(postexp));
}
}