許曉宇

摘要： 關(guā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引言

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

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

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

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

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

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

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

1算法描述

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

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

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

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

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

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

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

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

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

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

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

2算法實現(xiàn)

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

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

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

4結(jié)束語

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

參考文獻：

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

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

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

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

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

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

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

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

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

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