棧的應用——表達式求值

2019-11-11 01:49:21

字體：大中小

來源：轉載

供稿：網友

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

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