中綴表達式就是我們習慣的表達式比如說1+2*3，后綴表達式是計算機習慣的表達式。
1+2*3轉成后綴表達式后：123*+

中綴轉后綴算法：

- 遍歷中綴表達式中的數字和符號:
- 對于符號:
- 左括號:進棧
- 若棧頂符號優先級低:此符號進棧(默認棧頂若是左括號,左括號優先級最低)

• 若棧頂符號優先級不低:將棧頂符號彈出并輸出,之后進棧

• 右括號:將棧頂符號彈出并輸出,直到匹配左括號遍歷結束:將棧中的所有符號彈出并輸出

數字直接輸出:———————————結果：8

運算符要先判斷優先級，但現在棧為空直接將它進行壓棧

直接將左括號壓棧

數字直接輸出———————-結果：83

碰到運算符將他與當前棧頂比較，括號優先級最低所以-進棧

輸出—————結果：831

碰到右括號將棧頂符號彈出并輸出,直到匹配左括號 結果：831-
（括號會抵消掉）

乘號優先級比加高，*進棧

輸出——————–結果：831-5

此時以指向 \0 結束符將棧里的元素逐個彈出，結果：831-5*+

.h

//鏈式棧的節點 typedef struct LINKNODE {struct LINKNODE*next; }LinkNode;//鏈式棧 typedef struct LINKSTACK {LinkNode head;int size;}LinkStack;class linkstack { public:linkstack();~linkstack(); public:LinkStack* Stack;public://入棧void push_back(LinkStack* stack,LinkNode* data);//出棧void pop_back(LinkStack* stack);//返回棧頂元素LinkNode* Top_LinkStack(LinkStack* stack);//返回棧元素的個數int Size_LinkStack(LinkStack* stack);//清空棧void Clear_LinkStack(LinkStack* stack);};

.cpp

linkstack::linkstack() {Stack = new LinkStack;Stack->head.next = NULL;Stack->size = 0; }linkstack::~linkstack() {if (Stack == NULL){return;}delete Stack;}//入棧 void linkstack::push_back(LinkStack* stack, LinkNode* data) {if (stack == NULL || data == NULL){return;}data->next = stack->head.next;stack->head.next = data;stack->size++; }//出棧 void linkstack::pop_back(LinkStack* stack) {if (stack == NULL || stack->size == 0){return;}LinkNode* pNext = stack->head.next;stack->head.next = pNext->next;stack->size--; }//返回棧頂元素 LinkNode* linkstack::Top_LinkStack(LinkStack* stack) {if (stack == NULL || stack->size == 0){return NULL;}return stack->head.next; }//返回棧元素的個數 int linkstack::Size_LinkStack(LinkStack* stack) {if (stack == NULL ){return -1;}return stack->size; }//清空棧 void linkstack::Clear_LinkStack(LinkStack* stack) {if (stack == NULL || stack->size == 0){return;}stack->head.next = NULL;stack->size = 0; }

main.cpp

linkstack* s = new linkstack();//判斷是否是數字 int IsNumber(char c) {return c >= '0' && c <= '9'; }//判斷是否為左括號 int IsLeft(char c) {return c == '('; }//判斷是否為右括號 int IsRight(char c) {return c == ')'; }//判斷是否為運算符 int IsOperator(char c) {return c == '+' || c == '-' || c == '*' || c == '/'; }//返回運算符優先級 int GetPriority(char c) {if (c == '*' || c == '/'){return 2;}if (c == '+' || c == '-'){return 1;}return 0; }typedef struct MYCHAR {LinkNode node;char* p;}MyChar;//數字操作 void NuberOperate(char* p) {cout << *p; }//創建MyChar MyChar* CreateMyChar(char* p) {MyChar* mychar = new MyChar;mychar->p = p;return mychar; }//左括號操作 void LeftOperate(LinkStack* stack,char* p) {s->push_back(stack,(LinkNode*)CreateMyChar(p)); }//右括號操作 void RinghtOperate(LinkStack* stack) {//判斷棧中有沒有元素while (s->Size_LinkStack(s->Stack) >0){MyChar* mychar = (MyChar*)s->Top_LinkStack(s->Stack);//如果匹配到左括號if (IsLeft(*mychar->p)){s->pop_back(s->Stack);break;}//輸出cout << *mychar->p;//彈出s->pop_back(stack);//釋放內存delete mychar;} }//運算符操作 void OperatorOperator(LinkStack* stack,char* p) {//先取出棧頂元素MyChar* mychar = (MyChar*)s->Top_LinkStack(stack);if (mychar == NULL){s->push_back(stack, (LinkNode*)CreateMyChar(p));return;}//如果棧頂優先級低于當前字符優先級 直接入棧if (GetPriority(*mychar->p) < GetPriority(*p)){s->push_back(stack,(LinkNode*)CreateMyChar(p));return;}else //如果棧頂優先級不低{while (s->Size_LinkStack(stack) >0){MyChar* mychar2 = (MyChar*)s->Top_LinkStack(stack);//如果優先級低 當前符號入棧if (GetPriority(*mychar2->p) < GetPriority(*p)){s->push_back(stack,(LinkNode*)CreateMyChar(p));break;}//輸出cout <<*mychar2->p;//彈出s->pop_back(stack);//釋放內存delete mychar2;}}}int main() {char* str = "8+(3-1)*5";char* p = str;while (*p != '\0'){//如果是數字直接輸出if (IsNumber(*p)){NuberOperate(p);goto go;}//如果是左括號直接進棧if (IsLeft(*p)){LeftOperate(s->Stack, p);goto go;}//如果是右括號if (IsRight(*p)){RinghtOperate(s->Stack);goto go;}//如果是運算符if (IsOperator(*p)){OperatorOperator(s->Stack,p);goto go;}go:p++;}while (s->Size_LinkStack(s->Stack) >0){MyChar* mychar = (MyChar*)s->Top_LinkStack(s->Stack);cout << *mychar->p;s->pop_back(s->Stack);delete mychar;}delete s;return 0; }

結果：

總結

以上是生活随笔為你收集整理的栈的应用_中缀表达式转后缀表达式的全部內容，希望文章能夠幫你解決所遇到的問題。

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