基于棧結構，將中綴表達式轉換為后綴表達式的算法步驟是：

初始化運算符棧op;

將'='進棧;
從exp讀取字符ch;
while (ch!='\0')
{
? ? if (ch不為運算符)
　　　 ?將后續的所有數字均依次存放到postexp中,并以字符'#'標志數值串結束;
? ? else
? ? ? ?switch(Precede(op棧頂運算符,ch))
? ? ? ?{
? ? ? ?case '<': ? //棧頂運算符優先級低
? ? ? ? ? ? ?將ch進棧; ?從exp讀取下字符ch; ?break;
? ? ? ?case '=': ? //只有棧頂運算符為'(',ch為')'的情況
? ? ? ? ? ? ?退棧; 從exp讀取下字符ch; break;
? ? ? ?case '>': ? ?//棧頂運算符應先執行,所以出棧并存放到postexp中
? ? ? ? ? ? ?退棧運算符并將其存放到postexp中; break;
? ? ? }

}

/* *Copyright (c) 2017,煙臺大學計算機與控制工程學院 *All rights reserved. *文件名稱：項目7-實現將一個中綴表達式轉換為對應的后綴表達式的算法。例如，輸入(56-20)/(4+2)，輸出后綴表達式：:56#20#-4#2#+/要求在數字后加# *作 者：邵雪源 *完成日期：2017年12月13日 *版 本 號：v1.0 */ #include <stdio.h> #include <malloc.h> #define MaxOp 7 #define MaxSize 100 typedef char ElemType; typedef struct {ElemType data[MaxSize];int top; //棧指針 } SqStack; //順序棧類型定義 struct //設定運算符優先級 {char ch; //運算符int pri; //優先級 } lpri[]= {{'=',0},{'(',1},{'*',5},{'/',5},{'+',3},{'-',3},{')',6}}, rpri[]= {{'=',0},{'(',6},{'*',4},{'/',4},{'+',2},{'-',2},{')',1}}; void InitStack(SqStack *&s) {s=(SqStack *)malloc(sizeof(SqStack));s->top=-1; } void DestroyStack(SqStack *&s) {free(s); } int StackLength(SqStack *s) //返回棧中元素個數——棧長度 {return(s->top+1); } bool StackEmpty(SqStack *s) {return(s->top==-1); } bool Push(SqStack *&s,ElemType e) {if (s->top==MaxSize-1) //棧滿的情況，即棧上溢出return false;s->top++;s->data[s->top]=e;return true; } bool Pop(SqStack *&s,ElemType &e) {if (s->top==-1) //棧為空的情況，即棧下溢出return false;e=s->data[s->top];s->top--;return true; } bool GetTop(SqStack *s,ElemType &e) {if (s->top==-1) //棧為空的情況，即棧下溢出return false;e=s->data[s->top];return true; }void DispStack(SqStack *s) //輸出棧 {int i;for (i=s->top;i>=0;i--)printf("%c ",s->data[i]);printf("\n"); } 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; } bool InOp(char ch) //判斷ch是否為運算符 {if (ch=='(' || ch==')' || ch=='+' || ch=='-'|| ch=='*' || ch=='/')return true;elsereturn false; } int Precede(char op1,char op2) //op1和op2運算符優先級的比較結果 {if (leftpri(op1)==rightpri(op2))return 0;else if (leftpri(op1)<rightpri(op2))return -1;elsereturn 1; } void trans(char *exp,char postexp[]) //將算術表達式exp轉換成后綴表達式postexp {SqStack *opstack; //定義運算符棧int i=0; //i作為postexp的下標ElemType ch;InitStack(opstack); //用初始化棧運算為棧分配空間，務必要做Push(opstack, '=');while (*exp!='\0') //exp表達式未掃描完時循環{if (!InOp(*exp)) //為數字字符的情況{while (*exp>='0' && *exp<='9') //判定為數字{postexp[i++]=*exp;exp++;}postexp[i++]='#'; //用#標識一個數值串結束}else //為運算符的情況{GetTop(opstack, ch); //取得棧頂的運算符switch(Precede(ch ,*exp)){case -1: //棧頂運算符的優先級低:進棧Push(opstack, *exp);exp++; //繼續掃描其他字符break;case 0: //只有括號滿足這種情況Pop(opstack, ch); //將(退棧exp++; //繼續掃描其他字符break;case 1: //退棧并輸出到postexp中postexp[i++]=ch;Pop(opstack, ch);break;}}} //while (*exp!='\0')Pop(opstack, ch);while (ch!='=')//此時exp掃描完畢,退棧到'='為止{postexp[i++]=ch;Pop(opstack, ch);}postexp[i]='\0'; //給postexp表達式添加結束標識DestroyStack(opstack); } int main() {char exp[]="(56-20)/(4+2)"; //可將exp改為鍵盤輸入char postexp[200];trans(exp,postexp);printf("中綴表達式:%s\n",exp);printf("后綴表達式:%s\n",postexp);return 0; }

總結

以上是生活随笔為你收集整理的第五周实践项目7 后缀表达式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。