四則運算解析是編譯原理經典實踐，涉及詞法分析、語法分析、運算符優先級、括號嵌套。本文提供遞歸下降解析器與雙棧算法兩種工業級實現，支援 + - * / () 與小數運算。
Expression = Term { ('+' | '-') Term }*
Term = Factor { ('*' | '/') Factor }*
Factor = Number | '(' Expression ')' | ('+' | '-') Factor // 支援一元 +/-
Number = Digit+ ('.' Digit+)?public class RecursiveDescentParser {
private final String input;
private int pos = 0;
private char currentChar;
public RecursiveDescentParser(String input) {
this.input = input.replaceAll("\\s+", ""); // 移除空白
this.currentChar = input.isEmpty() ? '\0' : input.charAt(0);
}
public BigDecimal parse() {
BigDecimal result = expression();
if (pos < input.length()) throw new ParseException("Unexpected char at " + pos);
return result;
}
// Expression → Term { (+|-) Term }*
private BigDecimal expression() {
BigDecimal result = term();
while (match('+', '-')) {
char op = currentChar;
advance();
BigDecimal right = term();
result = op == '+' ? result.add(right) : result.subtract(right);
}
return result;
}
// Term → Factor { (*|/) Factor }*
private BigDecimal term() {
BigDecimal result = factor();
while (match('*', '/')) {
char op = currentChar;
advance();
BigDecimal right = factor();
if (op == '*') result = result.multiply(right);
else {
if (right.compareTo(BigDecimal.ZERO) == 0)
throw new ArithmeticException("Division by zero");
result = result.divide(right, 10, RoundingMode.HALF_UP);
}
}
return result;
}
// Factor → Number | '(' Expression ')' | (+|-) Factor
private BigDecimal factor() {
if (match('+', '-')) {
char op = currentChar;
advance();
BigDecimal val = factor();
return op == '-' ? val.negate() : val;
}
if (match('(')) {
advance(); // consume '('
BigDecimal result = expression();
if (!match(')')) throw new ParseException("Missing ')'");
advance(); // consume ')'
return result;
}
return number();
}
// Number → Digit+ ('.' Digit+)?
private BigDecimal number() {
StringBuilder sb = new StringBuilder();
while (matchDigit()) {
sb.append(currentChar);
advance();
}
if (match('.')) {
sb.append('.');
advance();
while (matchDigit()) {
sb.append(currentChar);
advance();
}
}
if (sb.length() == 0) throw new ParseException("Expected number at " + pos);
return new BigDecimal(sb.toString());
}
// 工具方法
private boolean match(char... chars) {
for (char c : chars) if (currentChar == c) return true;
return false;
}
private boolean matchDigit() { return currentChar >= '0' && currentChar <= '9'; }
private void advance() { currentChar = ++pos < input.length() ? input.charAt(pos) : '\0'; }
}public static void main(String[] args) {
String[] cases = {
"2+3*4", // 14
"(2+3)*4", // 20
"10/3", // 3.3333333333
"-5+3", // -2
"2*(-3+4)", // 2
"3.14*2", // 6.28
"((1+2)*3-4)/5" // 1
};
for (String expr : cases) {
try {
BigDecimal result = new RecursiveDescentParser(expr).parse();
System.out.printf("%-20s = %s%n", expr, result.stripTrailingZeros().toPlainString());
} catch (Exception e) {
System.err.printf("%-20s ERROR: %s%n", expr, e.getMessage());
}
}
}public class TwoStackCalculator {
private static final Map<Character, Integer> PRECEDENCE = Map.of(
'(', 3, '*', 2, '/', 2, '+', 1, '-', 1, ')', 0
);
public BigDecimal calculate(String expression) {
Deque<BigDecimal> numStack = new ArrayDeque<>();
Deque<Character> opStack = new ArrayDeque<>();
String expr = expression.replaceAll("\\s+", "");
StringBuilder numBuf = new StringBuilder();
for (int i = 0; i < expr.length(); i++) {
char ch = expr.charAt(i);
if (Character.isDigit(ch) || ch == '.') {
numBuf.append(ch);
continue;
}
// 遇到運算符，先壓入緩衝的數字
if (numBuf.length() > 0) {
numStack.push(new BigDecimal(numBuf.toString()));
numBuf.setLength(0);
}
if (ch == '(') {
opStack.push(ch);
} else if (ch == ')') {
while (!opStack.isEmpty() && opStack.peek() != '(')
compute(numStack, opStack.pop());
if (opStack.isEmpty()) throw new ParseException("Mismatched parentheses");
opStack.pop(); // 彈出 '('
} else if (PRECEDENCE.containsKey(ch)) {
while (!opStack.isEmpty() && opStack.peek() != '('
&& PRECEDENCE.get(ch) <= PRECEDENCE.get(opStack.peek())) {
compute(numStack, opStack.pop());
}
opStack.push(ch);
}
}
// 末尾數字入棧
if (numBuf.length() > 0) numStack.push(new BigDecimal(numBuf.toString()));
// 剩餘運算符計算
while (!opStack.isEmpty()) {
if (opStack.peek() == '(') throw new ParseException("Mismatched parentheses");
compute(numStack, opStack.pop());
}
if (numStack.size() != 1) throw new ParseException("Invalid expression");
return numStack.pop();
}
private void compute(Deque<BigDecimal> nums, char op) {
if (nums.size() < 2) throw new ParseException("Insufficient operands");
BigDecimal b = nums.pop(), a = nums.pop();
switch (op) {
case '+': nums.push(a.add(b)); break;
case '-': nums.push(a.subtract(b)); break;
case '*': nums.push(a.multiply(b)); break;
case '/':
if (b.compareTo(BigDecimal.ZERO) == 0) throw new ArithmeticException("Div by zero");
nums.push(a.divide(b, 10, RoundingMode.HALF_UP)); break;
}
}
}| 維度 | 遞歸下降 | 雙棧算法 |
|---|---|---|
| 代碼結構 | 清晰對應文法、易擴展函數/變量 | 緊湊、單函數完成 |
| 錯誤定位 | 精確到位置、語法錯誤信息豐富 | 較難定位具體位置 |
| 性能 | 遞歸調用開銷、深度受棧限制 | 迭代、無遞歸、極高性能 |
| 擴展性 | 易添加函數、變量、賦值、位運算 | 需重構優先級表、處理邏輯 |
| 適用場景 | DSL、腳本引擎、配置表達式 | 嵌入式、高頻計算、簡單四則運算 |
sin()、max()、if() 等內建函數Map<String, BigDecimal> variables 運行時賦值MathContext 統一精度與舍入模式四則運算解析器是理解編譯前端的最佳切入點。遞歸下降法結構清晰、擴展性強，適合構建 DSL 或腳本引擎；雙棧算法性能極致、代碼緊湊，適合高頻計算場景。掌握文法設計、優先級處理、錯誤恢復三大核心技能，即可舉一反三構建更複雜的表達式引擎。
