棧的應用——表達式求值

2019-11-11 02:29:53

字體：大中小

供稿：網(wǎng)友

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

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