表達式求值

表達式求值要解決的問題一般是輸入一個字符串表示的表達式，要求輸出它的值。當然也有變種比如表達式中是否包含括號，指數運算，含多少變量，判斷多個表達式是否等價，等等。

表達式一般需要先進行語法分析（grammer parsing）再求值，也可以邊分析邊求值，語法分析的作用是檢查輸入的字符串是否是一個合法的表達式，一般使用語法分析器（parser）解決。

表達式包含兩類字符：運算數和運算符。對於長度為 \(n\) 的表達式，藉助合適的分析方法，可以在 \(O(n)\) 的時間複雜度內完成分析與求值。

表達式樹與逆波蘭表達式

一種遞歸分析表達式的方法是，將表達式當成普通的語法規則進行分析，分析後拆分成如圖所示的表達式樹，然後在樹結構上自底向上進行運算。

表達式樹上進行 樹的遍歷 可以得到不同類型的表達式。算術表達式分為三種，分別是前綴表達式、中綴表達式、後綴表達式。中綴表達式是日常生活中最常用的表達式；後綴表達式是計算機容易理解的表達式。

• 前序遍歷對應前綴表達式（波蘭式）
• 中序遍歷對應中綴表達式
• 後序遍歷對應後綴表達式（逆波蘭式）

逆波蘭表達式（後綴表達式）是書寫數學表達式的一種形式，其中運算符位於其操作數之後。例如，以下表達式：

\[ a+b*c*d+(e-f)*(g*h+i) \]

可以用逆波蘭表達式書寫：

\[ abc*d*+ef-gh*i+*+ \]

因此，逆波蘭表達式與表達式樹一一對應。逆波蘭表達式不需要括號表示，它的運算順序是唯一確定的。

逆波蘭表達式的方便之處在於很容易在線性時間內計算。舉個例子：在逆波蘭表達式 \(3~2~\*~1~-\) 中，首先計算 \(3 \times 2 = 6\)（使用最後一個運算符，即棧頂運算符），然後計算 \(6 - 1 = 5\)。可以看到：對於一個逆波蘭表達式，只需要 維護一個數字棧，每次遇到一個運算符，就取出兩個棧頂元素，將運算結果重新壓入棧中。最後，棧中唯一一個元素就是該逆波蘭表達式的運算結果。該算法擁有 \(O(n)\) 的時間複雜度。

採用遞歸的辦法分析表達式是否成功，依賴於語法規則的設計是否合理，即，是否能夠成功地得到指定的表達式樹。例如：

\[ a+b*c \]

根據加號與乘號的運算優先級不同，該中綴表達式可能轉化為兩種不同的表達式樹。可見，語法規則的設計高度依賴於運算符的優先級。藉助運算符的優先級設計相應遞歸的語法規則，事實上是一件不容易的事情。

下文介紹的辦法將運算符與它的優先級視為一個整體，採用非遞歸的辦法，直接根據運算符的優先級來分析與計算表達式。

只含左結合的二元運算符的含括號表達式

考慮簡化的問題。假設所有運算符都是二元的：所有運算符都有兩個參數。並且所有運算符都是左結合的：如果運算符的優先級相等，則從左到右執行。允許使用括號。

對於這種類型的中綴表達式的計算，可以將其轉化為後綴表達式再進行計算。定義兩個 棧 來分別存儲運算符和運算數，每當遇到一個數直接放進運算數棧。每個運算符塊對應於一對括號，運算符棧只對於運算符塊的內部單調。每當遇到一個操作符時，要查找運算符棧中最頂部運算符塊中的元素，在運算符塊的內部保持運算符按照優先級降序進行適當的彈出操作，彈出的同時求出對應的子表達式的值。

以下部分用「輸出」表示輸出到後綴表達式，即將該數字放在運算數棧上，或者彈出運算符和兩個操作數，運算後再將結果壓回運算數棧上。從左到右掃描該中綴表達式：

1. 如果遇到數字，直接輸出該數字。
2. 如果遇到左括號，那麼將其放在運算符棧上。
3. 如果遇到右括號，不斷輸出棧頂元素，直至遇到左括號，左括號出棧。換句話説，執行一對括號內的所有運算符。
4. 如果遇到其他運算符，不斷輸出所有運算優先級大於等於當前運算符的運算符。最後，新的運算符入運算符棧。
5. 在處理完整個字符串之後，一些運算符可能仍然在堆棧中，因此把棧中剩下的符號依次輸出，表達式轉換結束。

以下是四個運算符 \(+\)、\(-\)、\(*\)、\(/\) 的此方法的實現：

示例代碼

bool delim(char c) { return c == ' '; }

bool is_op(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; }

int priority(char op) {
  if (op == '+' || op == '-') return 1;
  if (op == '*' || op == '/') return 2;
  return -1;
}

void process_op(stack<int>& st, char op) {  // 也可以用於計算後綴表達式
  int r = st.top();                         // 取出棧頂元素，注意順序
  st.pop();
  int l = st.top();
  st.pop();
  switch (op) {
    case '+':
      st.push(l + r);
      break;
    case '-':
      st.push(l - r);
      break;
    case '*':
      st.push(l * r);
      break;
    case '/':
      st.push(l / r);
      break;
  }
}

int evaluate(string& s) {  // 也可以改造為中綴表達式轉換後綴表達式
  stack<int> st;
  stack<char> op;
  for (int i = 0; i < (int)s.size(); i++) {
    if (delim(s[i])) continue;

    if (s[i] == '(') {
      op.push('(');  // 2. 如果遇到左括號，那麼將其放在運算符棧上
    } else if (s[i] == ')') {  // 3. 如果遇到右括號，執行一對括號內的所有運算符
      while (op.top() != '(') {
        process_op(st, op.top());
        op.pop();  // 不斷輸出棧頂元素，直至遇到左括號
      }
      op.pop();                // 左括號出棧
    } else if (is_op(s[i])) {  // 4. 如果遇到其他運算符
      char cur_op = s[i];
      while (!op.empty() && priority(op.top()) >= priority(cur_op)) {
        process_op(st, op.top());
        op.pop();  // 不斷輸出所有運算優先級大於等於當前運算符的運算符
      }
      op.push(cur_op);  // 新的運算符入運算符棧
    } else {            // 1. 如果遇到數字，直接輸出該數字
      int number = 0;
      while (i < (int)s.size() && isalnum(s[i]))
        number = number * 10 + s[i++] - '0';
      --i;
      st.push(number);
    }
  }

  while (!op.empty()) {
    process_op(st, op.top());
    op.pop();
  }
  return st.top();
}

這種隱式使用逆波蘭表達式計算表達式的值的算法的時間複雜度為 \(O(n)\)。通過稍微修改上述實現，還可以以顯式形式獲得逆波蘭表達式。

一元運算符與右結合的運算符

現在假設表達式還包含一元運算符，即只有一個參數的運算符。一元加號和一元減號是一元運算符的常見示例。

這種情況的一個區別是，需要確定當前運算符是一元運算符還是二元運算符。

注意到，在一元運算符之前一般有另一個運算符或開括號，如果一元運算符位於表達式的最開頭則沒有。在二元運算符之前，總是有一個運算數或右括號。因此，可以標記下一個運算符是否一元運算符。

此外，需要以不同的方式執行一元運算符和二元運算符，讓一元運算符的優先級高於所有二元運算符。應注意，一些一元運算符，例如一元加號和一元減號，實際上是右結合的。

右結合意味着，每當優先級相等時，必須從右到左計算運算符。

如上所述，一元運算符通常是右結合的。右結合運算符的另一個示例是求冪運算符。對於 \(a \wedge b \wedge c\)，通常被視為 \(a^{b^c}\)，而不是 \((a^b)^c\)。

為了正確地處理這類運算符，相應的改動是，如果優先級相等，將推遲運算符的出棧操作。

需要改動的代碼如下。將：

while (!op.empty() && priority(op.top()) >= priority(cur_op)) 

換成

while (!op.empty() &&
       ((left_assoc(cur_op) && priority(op.top()) >= priority(cur_op)) ||
        (!left_assoc(cur_op) && priority(op.top()) > priority(cur_op))))

其中 left_assoc 是一個函數，它決定運算符是否為左結合的。

這裏是二進制運算符 \(+\)、\(-\)、\(*\)、\(/\) 和一元運算符 \(+\) 和 \(-\) 的實現：

示例代碼

bool delim(char c) { return c == ' '; }

bool is_op(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; }

bool is_unary(char c) { return c == '+' || c == '-'; }

int priority(char op) {
  if (op < 0)  // unary operator
    return 3;
  if (op == '+' || op == '-') return 1;
  if (op == '*' || op == '/') return 2;
  return -1;
}

void process_op(stack<int>& st, char op) {
  if (op < 0) {
    int l = st.top();
    st.pop();
    switch (-op) {
      case '+':
        st.push(l);
        break;
      case '-':
        st.push(-l);
        break;
    }
  } else {  // 取出棧頂元素，注意順序
    int r = st.top();
    st.pop();
    int l = st.top();
    st.pop();
    switch (op) {
      case '+':
        st.push(l + r);
        break;
      case '-':
        st.push(l - r);
        break;
      case '*':
        st.push(l * r);
        break;
      case '/':
        st.push(l / r);
        break;
    }
  }
}

int evaluate(string& s) {
  stack<int> st;
  stack<char> op;
  bool may_be_unary = true;
  for (int i = 0; i < (int)s.size(); i++) {
    if (delim(s[i])) continue;

    if (s[i] == '(') {
      op.push('(');  // 2. 如果遇到左括號，那麼將其放在運算符棧上
      may_be_unary = true;
    } else if (s[i] == ')') {  // 3. 如果遇到右括號，執行一對括號內的所有運算符
      while (op.top() != '(') {
        process_op(st, op.top());
        op.pop();  // 不斷輸出棧頂元素，直至遇到左括號
      }
      op.pop();  // 左括號出棧
      may_be_unary = false;
    } else if (is_op(s[i])) {  // 4. 如果遇到其他運算符
      char cur_op = s[i];
      if (may_be_unary && is_unary(cur_op)) cur_op = -cur_op;
      while (!op.empty() &&
             ((cur_op >= 0 && priority(op.top()) >= priority(cur_op)) ||
              (cur_op < 0 && priority(op.top()) > priority(cur_op)))) {
        process_op(st, op.top());
        op.pop();  // 不斷輸出所有運算優先級大於等於當前運算符的運算符
      }
      op.push(cur_op);  // 新的運算符入運算符棧
      may_be_unary = true;
    } else {  // 1. 如果遇到數字，直接輸出該數字
      int number = 0;
      while (i < (int)s.size() && isalnum(s[i]))
        number = number * 10 + s[i++] - '0';
      --i;
      st.push(number);
      may_be_unary = false;
    }
  }

  while (!op.empty()) {
    process_op(st, op.top());
    op.pop();
  }
  return st.top();
}

參考資料

本頁面主要譯自博文 Разбор выражений. Обратная польская нотация 與其英文翻譯版 Expression parsing。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

延申閲讀

1. Operator-precedence_parser
2. Shunting yard algorithm

習題

1. 表達式求值（NOIP2013）
2. 後綴表達式
3. Transform the Expression

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, Anguei, hsfzLZH1, siger-young, HeRaNO, c8ef
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用