胡 云

(無(wú)錫廣播電視大學(xué),江蘇無(wú)錫 214011)

0 引 言

運(yùn)算符和運(yùn)算對(duì)象是表達(dá)式的兩個(gè)組成部分,根據(jù)運(yùn)算符計(jì)算對(duì)象的數(shù)量將其分為單目運(yùn)算符、雙目運(yùn)算符和三目運(yùn)算符[1-3].為便于理解,本研究?jī)H討論由雙目運(yùn)算符構(gòu)成的表達(dá)式.根據(jù)運(yùn)算符和運(yùn)算對(duì)象的相對(duì)位置關(guān)系可以將表達(dá)式分為前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式.實(shí)際應(yīng)用中,使用頻率最高的是中綴表達(dá)式,其運(yùn)算符的兩個(gè)運(yùn)算對(duì)象一個(gè)置于前面,另一個(gè)置于后面.人們習(xí)慣使用這種表達(dá)式形式,直觀上求值也相對(duì)容易,但在計(jì)算機(jī)上對(duì)其求值,因?yàn)橥瑫r(shí)要考慮運(yùn)算符的優(yōu)先級(jí)和結(jié)合性,就顯得比較困難.對(duì)此,本研究提出一種基于二叉樹(shù)的轉(zhuǎn)換方法.

1 傳統(tǒng)的轉(zhuǎn)換方法

通常,將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式的方法是:把每個(gè)運(yùn)算符的兩個(gè)運(yùn)算對(duì)象都移到它的后面,然后去除掉所有的括號(hào).因此在前綴表達(dá)式中,沒(méi)有括號(hào)運(yùn)算符,也沒(méi)有優(yōu)先級(jí)的差別.本研究討論的運(yùn)算符及其優(yōu)先級(jí)如表1所示.

表1 各個(gè)算術(shù)運(yùn)算符的優(yōu)先級(jí)

表1中,osp稱為棧外優(yōu)先級(jí),isp稱為棧內(nèi)優(yōu)先級(jí).右括號(hào)′)′具有最高的棧外優(yōu)先級(jí),處理時(shí)一遇到′)′立即將其壓入棧內(nèi),進(jìn)棧后,其棧內(nèi)優(yōu)先級(jí)變得很低,僅高于′#′,其目的是便于括號(hào)內(nèi)的其它運(yùn)算符進(jìn)棧.其它運(yùn)算符進(jìn)棧后優(yōu)先級(jí)數(shù)都減1.運(yùn)算符優(yōu)先級(jí)相等的情況只出現(xiàn)在括號(hào)匹配或棧底的′#′號(hào)與輸入流最后的′#′號(hào)匹配時(shí).前者將連續(xù)彈出位于棧頂?shù)倪\(yùn)算符,直至遇到′)′為止.然后將′)′退棧以成對(duì)消除括號(hào),后者將結(jié)束算法.

轉(zhuǎn)換后,表達(dá)式中運(yùn)算對(duì)象的次序不變,而運(yùn)算符的次序發(fā)生了變化,由處在兩個(gè)操作對(duì)象的中間變?yōu)樘幵趦蓚€(gè)運(yùn)算對(duì)象的前面,同時(shí)去掉了所有的括號(hào).轉(zhuǎn)換過(guò)程使用兩個(gè)棧,一個(gè)用來(lái)存放運(yùn)算符,另一個(gè)用來(lái)保存轉(zhuǎn)換得到的結(jié)果.對(duì)于存放運(yùn)算符的棧,先要在棧底放一個(gè)特殊運(yùn)算符,假定為′#′字符,讓它具有最低的運(yùn)算符優(yōu)先級(jí),假定為數(shù)值0.對(duì)中綴表達(dá)式字符串的掃描是從后向前進(jìn)行的.

算法具體描述如下:

(1)運(yùn)算符棧R和保存結(jié)果的棧D初始化,將結(jié)束符′#′壓入棧R,然后讀入中綴表達(dá)式字符串的最后一個(gè)字符ch.

(2)重復(fù)執(zhí)行以下步驟,直到第一個(gè)字符:①若ch是運(yùn)算對(duì)象直接壓入棧D,讀入前一個(gè)字符到ch.②若ch是運(yùn)算符,判斷ch的優(yōu)先級(jí)osp和棧R的棧頂運(yùn)算符op的優(yōu)先級(jí)isp:若osp(ch)>isp(op),將ch壓入棧R,讀入前一個(gè)字符到ch;若osp(ch)< isp(op),將棧R出棧的元素壓入到棧D中,繼續(xù)執(zhí)行步驟②;若osp(ch)=isp(op),說(shuō)明ch是字符′(′,對(duì)棧R執(zhí)行退棧操作,讀入前一個(gè)字符到ch.

(3)將棧R中各個(gè)元素依次出棧,再壓入到棧D中,直到出棧元素是字符′#′,然后將棧D各個(gè)元素依次出棧輸出,即得到轉(zhuǎn)換后的前綴表達(dá)式.

設(shè)以′#′字符作為結(jié)束符的中綴表達(dá)式已經(jīng)保存在s1字符串中,轉(zhuǎn)換后得到的前綴表達(dá)式存于s2字符串中.由中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式的規(guī)則可知:為了使轉(zhuǎn)換正確,需要設(shè)定2個(gè)棧.

將字符串s1表示的中綴表達(dá)式轉(zhuǎn)為前綴表達(dá)式算法的基本操作方法是,從后向前掃描中綴表達(dá)式中的每個(gè)字符,對(duì)不同類型的字符分別進(jìn)行處理.設(shè)定一個(gè)標(biāo)識(shí)flag,如果掃描到的是非數(shù)值字符則將flag置為0;如掃描到的是數(shù)值字符則將flag置為1.設(shè)定2個(gè)棧,一個(gè)是存放運(yùn)算符的棧R,另一個(gè)是保存轉(zhuǎn)換結(jié)果的棧D.如果掃描到的是空格,則看成分隔符,無(wú)需進(jìn)行處理;若掃描到的是右括號(hào),則將其壓入棧R中,等到以它為結(jié)束符的括號(hào)內(nèi)的表達(dá)式轉(zhuǎn)換完畢后再?gòu)棾鰲?同時(shí)將flag置為0;若掃描到的是左括號(hào),則說(shuō)明括號(hào)內(nèi)的中綴表達(dá)式已經(jīng)轉(zhuǎn)換結(jié)束,將棧R中從棧頂直到對(duì)應(yīng)右括號(hào)之間的運(yùn)算符依次出棧并壓入棧D內(nèi),同時(shí)將flag置為0;若掃描到的是運(yùn)算符,并且該運(yùn)算符的優(yōu)先級(jí)不小于棧R的棧頂運(yùn)算符的優(yōu)先級(jí)時(shí),將它壓入棧R內(nèi),同時(shí)將flag置為0;若掃描到的運(yùn)算符的優(yōu)先級(jí)小于棧R的棧頂運(yùn)算符的優(yōu)先級(jí)時(shí),將棧R的棧頂運(yùn)算符出棧并壓入棧D中,直到棧R的棧頂運(yùn)算符的優(yōu)先級(jí)大于或等于當(dāng)前運(yùn)算符的優(yōu)先級(jí)為止,然后將運(yùn)算符壓入棧R內(nèi),同時(shí)將flag置為0;當(dāng)中綴表達(dá)式字符串掃描結(jié)束時(shí)將棧R中剩余的所有元素依次出棧并壓入棧D內(nèi),最后將棧D中元素依次出棧保存在字符串s2中,再向s2末尾加上表達(dá)式結(jié)束符′#′和字符串結(jié)束符′

揭东县| 博白县| 永修县| 二手房| 金乡县| 和林格尔县| 石柱| 东乌珠穆沁旗| 四川省| 阳原县| 通城县| 长沙县| 重庆市| 临夏市| 白沙| 武定县| 油尖旺区| 桦川县| 延津县| 临湘市| 莱阳市| 松桃| 虞城县| 大田县| 抚顺县| 汝州市| 盐城市| 江都市| 香港 | 施甸县| 安顺市| 临安市| 方山县| 乌拉特后旗| 行唐县| 建水县| 池州市| 长阳| 从化市| 肇源县| 天气|