程式師世界 >> 編程語言 >> 更多編程語言 >> 編程綜合問答 >> 數據結構棧的應用-請教數據結構後綴表達式求值問題

數據結構棧的應用-請教數據結構後綴表達式求值問題

編輯：編程綜合問答

請教數據結構後綴表達式求值問題

要求是：設操作數：0，1，2，……，8，9（可擴充）；
運算符：+，—，*，/，（，），#（#號為結束）。
輸入中綴表達式，如：5+(4—2)*3 #，將其轉換成後綴表達式：542—3*+#，
然後計算，本例結果為11。
需要實現循環輸入表達式，我雖然寫了do-while卻總是無法實現循環，不知道問題出在哪裡。
代碼如下：
#include
#include
#include
#define Maxsize 100
typedef struct
{
char data[Maxsize]; //存放運算符
int top; //棧頂指針
}operation; //定義運算符棧
void Mid_post(char mid[],char post[])
{
char ch;
int i=0,j=0; //i作為mid的下標，j作為post的下標
operation op;
op.top=-1; //棧置空
ch=mid[i];
i++;
while(ch!='#')
{
switch(ch)
{
case '(': //若ch為左括號，則進棧
op.top++;
op.data[op.top]=ch;
break;
case ')': //若ch為右括號，則出棧，將其中的操作符賦給post[],直到棧頂為左括號
while(op.data[op.top]!='(')
{
post[j++]=op.data[op.top];
op.top--;
}
op.top--; //將棧頂指針減一
break;
case '+':
case '-':
while (op.top!=-1 && op.data[op.top]!='(') //'+'或'-'，優先級不大於棧頂任何運算符，棧頂出棧直到棧頂為左括號
{
post[j++]=op.data[op.top];
op.top--;
}
op.top++; //'+'或'-'進棧
op.data[op.top]=ch;
break;
case '*':
case '/':
while(op.top!=-1 && op.data[op.top]!='('
&& (op.data[op.top]=='*' || op.data[op.top]=='/'))//當棧頂運算符為'*'或'/'，棧頂出棧，直到棧頂不為'*''/',或遇到左括號
{
post[j++]=op.data[op.top];
op.top--;
}
op.top++;
op.data[op.top]=ch;
break;
case ' ':break;
default:
while(ch>='0' && ch<='9') //判定為數字
{
post[j++]=ch;
ch=mid[i++];
}
i--;
post[j++]='@'; //用'@'標識一個數值串結束
}
ch=mid[i];
i++;
}
while(op.top!=-1)
{
post[j++]=op.data[op.top];
op.top--;
}
post[j]='\0'; //給post表達式添加結束標識
}

struct //數值棧
{
float data[Maxsize]; //存放數值
int top; //棧頂指針
}st;

float Postcount(char post[]) //計算後綴表達式的值
{
float d;
char ch;
int i=0; //i作為post[]的下標
st.top=-1;
ch=post[i];i++;
while(ch!='\0')
{
switch(ch)
{
case '+' : st.data[st.top-1]=st.data[st.top-1] + st.data[st.top];
st.top--;break;
case '-' : st.data[st.top-1]=st.data[st.top-1] - st.data[st.top];
st.top--;break;
case '*' : st.data[st.top-1]=st.data[st.top-1] * st.data[st.top];
st.top--;break;
case '/' : if(st.data[st.top] != 0)
st.data[st.top-1]=st.data[st.top-1] / st.data[st.top];
else
{
printf("\n\t除零錯誤!\n");
exit(0); //異常退出
}
st.top--;break;
case '@' : st.top--;break;
default:
d=0; //將數字字符轉換成對應的數值存放到d中
while(ch>='0' && ch<='9') //判定為數字字符
{
d=10*d+ch-'0';
ch=post[i++];
}
st.top++;
st.data[st.top]=d;
}
ch=post[i++];
}
return st.data[st.top];
}
int main()
{
char p;
char post[100]={0},mid[100]={0};
float x;
do{
gets(mid);
Mid_post(mid,post);
x=Postcount(post);
printf("%f\n",x);
printf("是否繼續？\n");
fflush(stdin);
scanf("%c",&p);
}while(p=='Y' || p=='y');
return 0;
}