棧的應(yīng)用——表達(dá)式求值

2019-11-11 02:22:48

字體：大中小

供稿：網(wǎng)友

棧的應(yīng)用——表達(dá)式求值棧在數(shù)據(jù)結(jié)構(gòu)中應(yīng)用非常廣泛，表達(dá)式求值就是最典型的例子之一。1、 “表達(dá)式” = “第一操作數(shù)” + “運(yùn)算符” + “第二操作數(shù)” “操作數(shù)” = “簡(jiǎn)單變量” | “表達(dá)式” “簡(jiǎn)單變量” = “標(biāo)識(shí)符” | “無(wú)符號(hào)整數(shù)”2、 exp：a*b+（c-d/e）*f注意：前綴、中綴和后綴表示法都沒(méi)有括弧（1）前綴表示法：+*ab*-c/def 連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式；前綴式唯一的確定了運(yùn)算次序；（2）中綴表示法：a*b+c-d/e*f 中綴式丟失了括弧信息，致使運(yùn)算的次序不確定；（3）后綴表示法：ab*cde/-f*+ 運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算次序（因此，后綴式應(yīng)用最為廣泛）；每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式。結(jié)論：（1）操作數(shù)之間的相對(duì)次序不變；（2）運(yùn)算符的相對(duì)次序不同（中綴相同，但沒(méi)有括弧）；3、如何從后綴式求原表達(dá)式的值？先找運(yùn)算符，再找操作數(shù)。需要一個(gè)棧，依次遍歷后綴式字符，遇到操作數(shù)就進(jìn)棧，遇到運(yùn)算符就取出棧頂?shù)诙僮鲾?shù)，再取出棧頂?shù)谝徊僮鲾?shù)，兩個(gè)操作數(shù)和一個(gè)運(yùn)算符一起構(gòu)成一個(gè)最小表達(dá)式，即成為一個(gè)操作數(shù)再次進(jìn)棧。以此類推…… _________________________________________________________________________ exp： ab*cde/-f*+ stack：| a | | | | | a | b | | | | a*b | c | | | | a*b | c | d | | | a*b | c | d | e | | a*b | c | d/e | | | a*b | c-d/e | | | | a*b | c-d/e | f | | | a*b | (c-d/e)*f | | | | a*b + (c-d/e)*f | | | | 最后棧底的元素就是表達(dá)式的值！___________________________________________________________________________ 4、如何從原表達(dá)式求后綴式？需要一個(gè)棧，存儲(chǔ)運(yùn)算符（為了始終可比，可在棧底放‘#’，規(guī)定‘#’優(yōu)先級(jí)最低），遇到操作數(shù)直接送入后綴式。每一個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來(lái)定，在后綴式中，優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算發(fā)。具體步驟為：（1）設(shè)立運(yùn)算符棧；（2）設(shè)表達(dá)式的結(jié)束符為'#' , 預(yù)設(shè)運(yùn)算符棧的棧底為‘#’；（3）若當(dāng)前字符是操作數(shù)，則直接發(fā)給后綴式；（4）若當(dāng)前運(yùn)算符的優(yōu)先級(jí)高于棧頂運(yùn)算符，則進(jìn)棧；（5）否則，推出棧頂運(yùn)算符發(fā)給后綴式；（6）‘（’ 對(duì)它之后的運(yùn)算符起隔離作用，‘）’ 可視為自相應(yīng)左括弧開(kāi)始的表達(dá)式；上代碼……

——————————————————————————————————————————