Day 068-Q4 — 再帰下降構文解析（Recursive Descent Parser・式木・変数評価）

問題

変数と四則演算・べき乗・括弧を含む数式を構文解析し、変数に値を代入して評価せよ。

文法（EBNF）:

expr   ::= term (('+' | '-') term)*
term   ::= power (('*' | '/') power)*
power  ::= unary ('^' unary)*   ← 右結合
unary  ::= '-' unary | factor
factor ::= '(' expr ')' | NUMBER | VARIABLE

入出力例

2
(a+b)*(a-b)
2
a 3
b 2
x^(y+1)+z*2
3
x 2
y 3
z 5

5
26

(3+2)*(3-2) = 5*1 = 5。2^(3+1)+5*2 = 2^4+10 = 16+10 = 26。

概念図: 演算子優先度階層と呼び出しグラフ

ヒント（段階的開示）

def parse_power(self):
    """右結合: a^b^c = a^(b^c)"""
    base = self.parse_unary()
    if self.peek() == '^':
        self.consume('^')
        exp = self.parse_power()  # ← 再帰で右結合
        return int(base ** exp)
    return base

def parse_expr(self):
    """左結合: whileループ"""
    val = self.parse_term()
    while self.peek() in ('+', '-'):
        op = self.consume()
        r = self.parse_term()
        val = val + r if op == '+' else val - r
    return val

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline

class Parser:
    def __init__(self, s, var):
        self.s = s.replace(' ', '')
        self.pos = 0
        self.var = var

    def peek(self):
        if self.pos < len(self.s):
            return self.s[self.pos]
        return ''

    def consume(self, c=None):
        ch = self.s[self.pos]
        if c is not None:
            assert ch == c
        self.pos += 1
        return ch

    def parse_expr(self):
        val = self.parse_term()
        while self.peek() in ('+', '-'):
            op = self.consume()
            r = self.parse_term()
            val = val + r if op == '+' else val - r
        return val

    def parse_term(self):
        val = self.parse_power()
        while self.peek() in ('*', '/'):
            op = self.consume()
            r = self.parse_power()
            val = val * r if op == '*' else int(val / r)
        return val

    def parse_power(self):
        base = self.parse_unary()
        if self.peek() == '^':
            self.consume('^')
            exp = self.parse_power()  # 右結合
            return int(base ** exp)
        return base

    def parse_unary(self):
        if self.peek() == '-':
            self.consume('-')
            return -self.parse_unary()
        return self.parse_factor()

    def parse_factor(self):
        ch = self.peek()
        if ch == '(':
            self.consume('(')
            val = self.parse_expr()
            self.consume(')')
            return val
        elif ch.isdigit():
            num = 0
            while self.peek().isdigit():
                num = num * 10 + int(self.consume())
            return num
        elif ch.islower():
            name = self.consume()
            return self.var[name]
        else:
            raise ValueError(f"Unexpected: {ch!r}")

def main():
    Q = int(input())
    out = []
    for _ in range(Q):
        expr = input().strip()
        m = int(input())
        var = {}
        for _ in range(m):
            v, val = input().split()
            var[v] = int(val)
        parser = Parser(expr, var)
        out.append(str(parser.parse_expr()))
    print('\n'.join(out))

main()

Step-by-Step 解説

Step 1: 優先度階層の設計

Step 2: 右結合べき乗

a^b^c は a^(b^c) と解釈される（右結合）。parse_power 内で ^ を見つけたら右辺を parse_power() で再帰的に解析することで自動的に右結合になる。左結合の + や * は while ループで処理する点と対比して理解する。

Step 3: 整数除算の注意点

Python の // は切り捨て除算で、負数の場合に挙動が異なる（-7 // 2 = -4）。ゼロ方向への切り捨てが必要な場合は int(a/b) を使う。

Step 4: AST 拡張

今回は値を直接返す評価器だが、Node クラスを使って抽象構文木（AST）を構築し、後から複数回評価・最適化・シンボリック微分などに活用できる。

Step 5: 計算量

よくあるミス

次のステップ

発展問題: 数式のシンボリック微分（式木をASTとして構築し、微分規則を適用）。Pratt Parser（Top-Down Operator Precedence）による汎用実装。

自己評価