基于雙棧結構的中綴表達式算法設計與實現

許曉宇

摘要： 關鍵詞： 中圖分類號： 文獻標志碼： A文章編號： 2095-2163（2017）06-0108-03

Abstract： The conventional algorithm calculating infix expression is to convert infix expressions into postfix expression，which has conversion intermediate process； this paper designs an algorithm based on dual stack structure， according to the inherent human thinking from left to right to directly calculate the infix expression， using only simple singular group to act as a data structure. During the process of the pretreatment， respectively restore the operators into symbol array stack and store values into real array stack. In the next calculation section， with the help of C language powerful circulation control ability， traverse the symbols stack， according to priority push and pop operators， call the real array double stack data in monocular and binocular operation， calculate the deposit， once again store in the top of the stack until the symbol stack is empty. Therefore， real array in the top of the stack is the calculation results. The experimental results show that the algorithm can effectively deal with monocular and binocular calculations， as well as Brackets.

0引言

中綴表達式的求解是算法與數據結構中的經典問題，也是程序設計中的一個不可回避的熱點問題，算法的邏輯描述相對簡單，但實現起來很多細節處理偏難。對于中綴表達式的算法設計，大致可以分為兩類：一類是依據物理計算機固有處理方式的特性去設計算法，另一類是依據人的固有思維習慣去設計算法。

多數學者，都只選擇第一類算法[1]，由于計算機擅長處理不帶優先級的逆波蘭表達式（即后綴表達式），因此，這類算法中對“中綴表達式的求值”問題轉換成了兩步：第一步將中綴表達式轉換成后綴表達式，第二步對后綴表達式的求值計算。在算法設計的過程中，根據具體選擇數據結構的不同，又分為基于數組的棧結構實現和基于二叉樹的棧結構實現。每種實現又可以引出基于不同的程序設計語言的各種版本的源代碼。還有一些學者將中綴表達式轉換成前綴表達式[2-3]進行求值。

本文算法則另辟蹊徑，選擇了依據人的固有思維習慣去設計算法，人類處理算術問題方法就是中綴表示式的直接處理方式，一般是按從左到右的順序，依據運算符的優先級進行計算。讓計算機模擬人類，直接對中綴表達式提供處理，需要從左到右遍歷中綴表達式，需要分優先級設計計算，需要一次性直接完成計算[4-5]。但計算機畢竟不是人類，所以就隱含了一定的問題，內容分析如下

1）從鍵盤或文本輸入框中，輸入的是字符串，如何變成運算符、數值。

2）優先級的設置能否與人類一樣。

3）如何一次性從左到右，直接裝入一目、二目運算符如“（、）、+、-、*、/、^、正、負”，并按優先級展開計算。

本文在算法設計時，使用了兩個數組棧結構[6-8]：一個放運算符，一個放操作數值，同時在算法的實現方式上用兩重循環控制的遞推方式替代遞歸方式，用數組和下標指針的移動替代棧結構棧頂元素的彈出與壓入。

1算法描述

1.1對中綴表達式的預處理

優先級次數高低遵循人類的純粹的數學中的計算優先級，設置的數值越大代表優先級越高，特別“（”入棧前及入棧后略有不同，壓棧前“（”優先級最高，壓棧后“（” 最低，假定只針對上述運算符，那么優先級設置如表1所示。

1.2計算核心為雙重循環控制遍歷雙棧結構

本文在算法設計時，使用了兩個數組充當棧結構[9-10]：一個放運算符，一個放操作數值，同時在算法的實現方式上用兩重循環控制的遞推方式替代遞歸方式，用數組和下標指針的移動替代棧結構棧頂元素的彈出與壓入。

從左到右依次遍歷預處理后的字符串，每次遍歷1個，直到遇到“等號”結束。設計解析闡釋如下：

1）如果遇到字符串是數值X，那么就壓入數值棧內。

2）如果遇到的是運算符，判斷棧是否為空：若為空，當前的符號壓棧，本次循環結束；否則，將當前的符號，與符號棧內所有的運算符進行循環比較，直到本次循環結束。

若當前的符號是“）”并且符號棧棧頂是“（”，那么直接彈出棧頂“（”，右括號“）”直接丟棄，循環結束。

若當前的符號的優先級小于等于棧頂的運算符，彈出棧頂運算符，同時依據此棧頂運算符的目次，從數值棧內彈出數值進行計算，然后再將計算結果，壓入數值棧。繼續做當前符號和棧頂元素的判斷，直到棧空，將當前符號壓入棧內，結束循環。endprint

若當前的符號的優先級大于棧頂運算符直接壓棧。

3）如果當前棧不空，則依次彈出棧內運算符，依次計算，棧頂數據[9]為最終計算結果。

2算法實現

2.1數據定義

用戶輸入的中綴表達式字符串定義為：char origin1[200]；預處理后的標準形式字符串char s[80]；存放運算符的字符數組char fuhao[80]；初次存放臨時數值字符串chrar shuzhi[80]，存放操作數數值的雙精度數組double num[20]；2個棧頂下標指示器int j，k；

2.2數據的賦值

4結束語

通過實驗不難發現本算法計算能力較強，對于人為多重括號的情況、正負號的情況都可以進行良好優化處理，使用數組棧結構，程序的空間效率較高。當然，文中沒有過多考慮程序健壯性，比如中綴表達式合法性檢查，也未能增加各種進制的轉換函數，不能方便進行各種進制的中綴表達式計算。

參考文獻：

[1] 胡云，毛萬年. 一種將中綴表達式轉換為后綴表達式的新方法[J]. 成都大學學報（自然科學版），2008，27（1）：52-55.

[2] 曹曉麗，潘穎. 一種利用棧實現中綴表達式向前綴表達式轉換方法的改進[J]. 甘肅科技，2006，22（11）：64-66，38.

[3] 劉任任. 中綴表達式到前綴表達式的快速算法[J]. 湘潭大學自然科學學報，1988，10（4）：96-99.

[4] 李艷玲. 數據結構中實現表達式求值算法的巧妙轉換[J]. 職大學報（自然科學版），2005（4）：62-63.

[5] 王迤冉，王華東. 表達式求值的一種實現方法[J]. 周口師范高等專科學校學報，2001，18（2）：31-33.

[6] 王淑禮，王新霞. 算術表達式求值算法實現的難點剖析[J]. 福建電腦，2012，28（3）：55-56.

[7] 李世華，劉曉娟，姜晨，等. 關于表達式求值的算法研究與實現[J]. 甘肅科技，2011，27（1）：11-15.

[8] 蘭美輝，楊平. 基于棧結構的算術表達式求值算法研究[J]. 曲靖師范學院學報，2014，33（3）：57-59.

[9] 王紅奎，肖榮. 基于棧結構的浮點型數據表達式求值算法[J]. 南昌航空工業學院學報（自然科學版），2004，18（3）：87-89.

[10]李橙，丁國棟. 棧在表達式求值中的應用[J]. 電腦知識與技術，2014，10（34）：8156-8157，8164.endprint