您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計疑難解答

字符串表達式求值：從遞歸下降解析器到 Shunting Yard 算法的完整實現指南

編輯：程式設計疑難解答

問題定義

實現函數 double evaluate(const char *expr)，輸入合法算術表達式字符串 (如 "(1+2)*3-4")，支持運算符 + - * / ( )，操作數為非負整數，返回計算結果 (double)。

核心挑戰

運算符優先級：* / > + -
括號改變優先級，支持嵌套
左結合性：1-2-3 = (1-2)-3
多位數解析："123" → 123
空白字符忽略 (可選增強)

方案一：遞歸下降解析器 (推薦，代碼清晰、易擴展)

文法定義 (EBNF)：


expression = term { ('+' | '-') term } ;
term       = factor { ('*' | '/') factor } ;
factor     = number | '(' expression ')' ;
number     = digit { digit } ;

每條產生式對應一個函數，自然體現優先級。

C 語言完整實現


#include 
#include 
#include 

typedef struct {
    const char *str;
    int pos;
} Parser;

double parse_expression(Parser *p);
double parse_term(Parser *p);
double parse_factor(Parser *p);
double parse_number(Parser *p);

void skip_spaces(Parser *p) {
    while (p->str[p->pos] && isspace(p->str[p->pos])) p->pos++;
}

double parse_number(Parser *p) {
    skip_spaces(p);
    double val = 0;
    int start = p->pos;
    while (isdigit(p->str[p->pos])) {
        val = val * 10 + (p->str[p->pos] - '0');
        p->pos++;
    }
    if (p->pos == start) { fprintf(stderr, "Error: Expected number at pos %d\n", p->pos); exit(1); }
    return val;
}

double parse_factor(Parser *p) {
    skip_spaces(p);
    if (p->str[p->pos] == '(') {
        p->pos++; // consume '('
        double val = parse_expression(p);
        skip_spaces(p);
        if (p->str[p->pos] != ')') { fprintf(stderr, "Error: Missing ')' at pos %d\n", p->pos); exit(1); }
        p->pos++; // consume ')'
        return val;
    }
    return parse_number(p);
}

double parse_term(Parser *p) {
    double val = parse_factor(p);
    while (1) {
        skip_spaces(p);
        char op = p->str[p->pos];
        if (op != '*' && op != '/') break;
        p->pos++;
        double rhs = parse_factor(p);
        if (op == '*') val *= rhs;
        else {
            if (rhs == 0) { fprintf(stderr, "Error: Division by zero\n"); exit(1); }
            val /= rhs;
        }
    }
    return val;
}

double parse_expression(Parser *p) {
    double val = parse_term(p);
    while (1) {
        skip_spaces(p);
        char op = p->str[p->pos];
        if (op != '+' && op != '-') break;
        p->pos++;
        double rhs = parse_term(p);
        if (op == '+') val += rhs;
        else val -= rhs;
    }
    return val;
}

double evaluate(const char *expr) {
    Parser p = {expr, 0};
    double result = parse_expression(&p);
    skip_spaces(&p);
    if (p.str[p.pos] != '\0') { fprintf(stderr, "Error: Unexpected char '%c' at pos %d\n", p.str[p.pos], p.pos); exit(1); }
    return result;
}

int main() {
    printf("%f\n", evaluate("(1+2)*3-4"));   // 5.000000
    printf("%f\n", evaluate("10/3"));        // 3.333333
    printf("%f\n", evaluate("2*(3+4)/5"));   // 2.800000
    return 0;
}

方案二：Shunting Yard 算法 (中綴轉後綴 + 後綴求值，經典編譯器技術)

適合需顯式構建 AST、支持更多運算符/函數的場景。


// 核心邏輯 (偽代碼)
輸出隊列: 數值
運算符棧: 運算符

掃描 token:
  若數值 -> 輸出隊列
  若運算符 o1:
    while 棧頂運算符 o2 且 (o2 優先級 > o1 或 (同級且左結合) 且 o2 != '('):
      弹出 o2 到輸出隊列
    壓入 o1
  若 '(' -> 壓入棧
  若 ')' -> 弹出運算符到輸出隊列 直到遇到 '('，彈出 '('

掃描結束 -> 彈出剩餘運算符到輸出隊列

// 後綴求值
掃描後綴 token:
  若數值 -> 壓值棧
  若運算符 -> 彈出兩值 計算 壓回結果
最終值棧頂即結果

方案對比與選型建議

維度	遞歸下降	Shunting Yard
代碼複雜度	低 (文法直映函數)	中 (雙棧管理)
錯誤定位	精確 (行/列號易集成)	較難 (需額外記錄位置)
擴展性 (函數/一元運算符/賦值)	極強 (修改文法即可)	中等 (需調整優先級表、棧邏輯)
性能	遞歸開銷微小，現代編譯器優化良好	迭代無遞歸，極大表達式略優
適用場景	解析器/編譯器前端、配置語言、DSL、教學	表達式計算器、舊系統移植、無遞歸環境

工程化增強清單

錯誤恢復：遇錯誤跳過至下一同步點 (如 ; 或 )) 繼續解析，報告多錯誤。
變量支持：符號表 map，factor 增加標識符分支。
函數支持：factor 識別 sin( cos( 等，調用 math.h。參數列表解析 expression {',' expression}。
整數/大整數模式：模板化數值類型，避免浮點精度問題。
單元測試：覆蓋優先級、括號嵌套、除零、非法字符、空白容忍、長整數溢出等用例。