實作一個可以處理加減乘數運算的中綴表達式轉換字尾表達式的程式:
一個輸入中綴表達式inOrder
一個輸出池pool
一個緩存棧stack
從前至後逐字讀取inOrder
(1)操作數:直接輸出到pool
(2)操作符:判斷目前操作符與stack[top]操作符的優先級
<1>目前操作符優先級高于stack[top]:将目前操作符添加到stack中;
<2>目前操作符優先級低于或等于stack[top]:從stack[top]開始出棧,直到stack[top]優先級高于目前操作符,然後将目前操作符入棧;
(3)當inOrder周遊結束,如果stack非空,反轉stack,添加到pool尾
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
在上個程式的基礎上,進一步考慮下邊的幾點:
(4)加入括号之後,“(”擁有最高優先級,也就是說,遇到“(”就放到stack中就好了;
(5)遇到“)”的操作也比較簡單,直接把stack中的元素逐一彈出到pool,直到彈出“(”;
此時需要新的操作符規則:
(5)操作符:判斷目前操作符與stack[top]操作符的優先級
<1>目前操作符優先級高于stack[top]或者stack[top]==‘(’:将目前操作符添加到stack中;
<2>目前操作符優先級低于或等于stack[top]:從stack[top]開始出棧,直到stack[top]優先級高于目前操作符或者stack[top]為“(”,然後将目前操作符入棧;
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIiZpdmLlR2bjlHcvN2LcNXZnFWbp9CXt92YuM3ZvxmYuNmLu9Wbt92Yvw1LcpDc0RHaiojIsJye.gif)
輸出:
abc*+de*f+g*+
本文轉自ZH奶酪部落格園部落格,原文連結:http://www.cnblogs.com/CheeseZH/p/4581771.html,如需轉載請自行聯系原作者