基于雙棧結(jié)構(gòu)的中綴表達(dá)式算法設(shè)計(jì)與實(shí)現(xiàn)

許曉宇

摘要： 關(guān)鍵詞： 中圖分類號： 文獻(xiàn)標(biāo)志碼： 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引言

中綴表達(dá)式的求解是算法與數(shù)據(jù)結(jié)構(gòu)中的經(jīng)典問題，也是程序設(shè)計(jì)中的一個不可回避的熱點(diǎn)問題，算法的邏輯描述相對簡單，但實(shí)現(xiàn)起來很多細(xì)節(jié)處理偏難。對于中綴表達(dá)式的算法設(shè)計(jì)，大致可以分為兩類：一類是依據(jù)物理計(jì)算機(jī)固有處理方式的特性去設(shè)計(jì)算法，另一類是依據(jù)人的固有思維習(xí)慣去設(shè)計(jì)算法。

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

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

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

2）優(yōu)先級的設(shè)置能否與人類一樣。

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

本文在算法設(shè)計(jì)時(shí)，使用了兩個數(shù)組棧結(jié)構(gòu)[6-8]：一個放運(yùn)算符，一個放操作數(shù)值，同時(shí)在算法的實(shí)現(xiàn)方式上用兩重循環(huán)控制的遞推方式替代遞歸方式，用數(shù)組和下標(biāo)指針的移動替代棧結(jié)構(gòu)棧頂元素的彈出與壓入。

1算法描述

1.1對中綴表達(dá)式的預(yù)處理

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

1.2計(jì)算核心為雙重循環(huán)控制遍歷雙棧結(jié)構(gòu)

本文在算法設(shè)計(jì)時(shí)，使用了兩個數(shù)組充當(dāng)棧結(jié)構(gòu)[9-10]：一個放運(yùn)算符，一個放操作數(shù)值，同時(shí)在算法的實(shí)現(xiàn)方式上用兩重循環(huán)控制的遞推方式替代遞歸方式，用數(shù)組和下標(biāo)指針的移動替代棧結(jié)構(gòu)棧頂元素的彈出與壓入。

從左到右依次遍歷預(yù)處理后的字符串，每次遍歷1個，直到遇到“等號”結(jié)束。設(shè)計(jì)解析闡釋如下：

1）如果遇到字符串是數(shù)值X，那么就壓入數(shù)值棧內(nèi)。

2）如果遇到的是運(yùn)算符，判斷棧是否為空：若為空，當(dāng)前的符號壓棧，本次循環(huán)結(jié)束；否則，將當(dāng)前的符號，與符號棧內(nèi)所有的運(yùn)算符進(jìn)行循環(huán)比較，直到本次循環(huán)結(jié)束。

若當(dāng)前的符號是“）”并且符號棧棧頂是“（”，那么直接彈出棧頂“（”，右括號“）”直接丟棄，循環(huán)結(jié)束。

若當(dāng)前的符號的優(yōu)先級小于等于棧頂?shù)倪\(yùn)算符，彈出棧頂運(yùn)算符，同時(shí)依據(jù)此棧頂運(yùn)算符的目次，從數(shù)值棧內(nèi)彈出數(shù)值進(jìn)行計(jì)算，然后再將計(jì)算結(jié)果，壓入數(shù)值棧。繼續(xù)做當(dāng)前符號和棧頂元素的判斷，直到?？?，將當(dāng)前符號壓入棧內(nèi)，結(jié)束循環(huán)。endprint

若當(dāng)前的符號的優(yōu)先級大于棧頂運(yùn)算符直接壓棧。

3）如果當(dāng)前棧不空，則依次彈出棧內(nèi)運(yùn)算符，依次計(jì)算，棧頂數(shù)據(jù)[9]為最終計(jì)算結(jié)果。

2算法實(shí)現(xiàn)

2.1數(shù)據(jù)定義

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

2.2數(shù)據(jù)的賦值

4結(jié)束語

通過實(shí)驗(yàn)不難發(fā)現(xiàn)本算法計(jì)算能力較強(qiáng)，對于人為多重括號的情況、正負(fù)號的情況都可以進(jìn)行良好優(yōu)化處理，使用數(shù)組棧結(jié)構(gòu)，程序的空間效率較高。當(dāng)然，文中沒有過多考慮程序健壯性，比如中綴表達(dá)式合法性檢查，也未能增加各種進(jìn)制的轉(zhuǎn)換函數(shù)，不能方便進(jìn)行各種進(jìn)制的中綴表達(dá)式計(jì)算。

參考文獻(xiàn)：

[1] 胡云，毛萬年. 一種將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的新方法[J]. 成都大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，27（1）：52-55.

[2] 曹曉麗，潘穎. 一種利用棧實(shí)現(xiàn)中綴表達(dá)式向前綴表達(dá)式轉(zhuǎn)換方法的改進(jìn)[J]. 甘肅科技，2006，22（11）：64-66，38.

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

[4] 李艷玲. 數(shù)據(jù)結(jié)構(gòu)中實(shí)現(xiàn)表達(dá)式求值算法的巧妙轉(zhuǎn)換[J]. 職大學(xué)報(bào)（自然科學(xué)版），2005（4）：62-63.

[5] 王迤冉，王華東. 表達(dá)式求值的一種實(shí)現(xiàn)方法[J]. 周口師范高等?？茖W(xué)校學(xué)報(bào)，2001，18（2）：31-33.

[6] 王淑禮，王新霞. 算術(shù)表達(dá)式求值算法實(shí)現(xiàn)的難點(diǎn)剖析[J]. 福建電腦，2012，28（3）：55-56.

[7] 李世華，劉曉娟，姜晨，等. 關(guān)于表達(dá)式求值的算法研究與實(shí)現(xiàn)[J]. 甘肅科技，2011，27（1）：11-15.

[8] 蘭美輝，楊平. 基于棧結(jié)構(gòu)的算術(shù)表達(dá)式求值算法研究[J]. 曲靖師范學(xué)院學(xué)報(bào)，2014，33（3）：57-59.

[9] 王紅奎，肖榮. 基于棧結(jié)構(gòu)的浮點(diǎn)型數(shù)據(jù)表達(dá)式求值算法[J]. 南昌航空工業(yè)學(xué)院學(xué)報(bào)（自然科學(xué)版），2004，18（3）：87-89.

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