20576: printExp

http://cs101.openjudge.cn/practice/20576/

输出中缀表达式(去除不必要的括号)

输入

一个字串

输出

一个字串

样例输入

( not ( True or False ) ) and ( False or True and True )

样例输出

not ( True or False ) and ( False or True and True )

题意：这三个操作符：not：优先级最高，and：其次，or：优先级最低。手写一个完整的Shunting Yard + AST 构造 + 打印

思路：基于优先级的通用中缀打印

核心思想：

给每个节点定义一个优先级值（not=3, and=2, or=1）。
打印时，仅当子节点的优先级低于父节点时加括号。
not 是单目操作符，只处理一个子节点。
True、False 优先级设为 4（最高，永远不加括号）。

python

class BinaryTree:
    def __init__(self, root, left=None, right=None):
        self.root = root
        self.leftChild = left
        self.rightChild = right

def postorder(string):  # 中缀改后缀 (Shunting Yard)
    opStack, postList = [], []
    inList = string.split()
    prec = {'(': 0, 'or': 1, 'and': 2, 'not': 3}
    for word in inList:
        if word == '(':
            opStack.append(word)
        elif word == ')':
            while opStack and opStack[-1] != '(':
                postList.append(opStack.pop())
            opStack.pop()
        elif word in ('True', 'False'):
            postList.append(word)
        else:  # operator
            while opStack and prec[word] <= prec[opStack[-1]]:
                postList.append(opStack.pop())
            opStack.append(word)
    while opStack:
        postList.append(opStack.pop())
    return postList

def buildParseTree(infix):
    postList = postorder(infix)
    stack = []
    for word in postList:
        if word == 'not':
            child = stack.pop()
            stack.append(BinaryTree('not', child))
        elif word in ('True', 'False'):
            stack.append(BinaryTree(word))
        else:
            right, left = stack.pop(), stack.pop()
            stack.append(BinaryTree(word, left, right))
    return stack[-1]

# 定义运算符优先级
priority = {'or': 1, 'and': 2, 'not': 3, 'True': 4, 'False': 4}

def printTree(tree):
    """返回 token 列表"""
    root = tree.root
    if root in ('True', 'False'):
        return [root]

    if root == 'not':
        child = tree.leftChild
        # 若子优先级更低则加括号
        child_tokens = printTree(child)
        if priority[child.root] < priority[root]:
            child_tokens = ['('] + child_tokens + [')']
        return ['not'] + child_tokens

    # 二元操作符 and/or
    left, right = tree.leftChild, tree.rightChild
    left_tokens = printTree(left)
    right_tokens = printTree(right)
    if priority[left.root] < priority[root]:
        left_tokens = ['('] + left_tokens + [')']
    if priority[right.root] < priority[root]:
        right_tokens = ['('] + right_tokens + [')']
    return left_tokens + [root] + right_tokens

def main():
    infix = input().strip()
    Tree = buildParseTree(infix)
    print(' '.join(printTree(Tree)))

if __name__ == "__main__":
    main()

直接利用 Python 自带的 ast 模块来完成解析与遍历，无需手写语法分析器。因为 ast.parse() 能正确识别 Python 布尔表达式（and/or/not/True/False）的语法树。

✅ 改写思路（使用 ast）

直接用 ast.parse(expr, mode='eval') 将输入的布尔表达式解析为抽象语法树（AST）。
递归遍历 AST，根据节点类型 (BoolOp, UnaryOp, NameConstant 等) 输出字符串。
根据运算符优先级，仅在必要时加括号。

优先级设定为：

not: 3
and: 2
or : 1

当子表达式优先级低于父表达式时，才加括号。

python

import ast
import sys

# 优先级： or=1, and=2, not=3
PREC = {
    ast.Or: 1,
    ast.And: 2,
    ast.Not: 3
}

def get_prec(node):
    """返回节点的优先级（数字越大优先级越高）。默认常量/名称优先级最高。"""
    if isinstance(node, ast.BoolOp):
        return PREC[type(node.op)]
    if isinstance(node, ast.UnaryOp):
        return PREC[type(node.op)]
    # 常量或其它原子表达式
    return 4

def to_str(node, parent_prec=0):
    """将 AST 节点转为 token 风格的字符串（带空格），根据 parent_prec 决定是否需要外层括号。"""
    # BoolOp: values 列表（and/or）
    if isinstance(node, ast.BoolOp):
        op = 'and' if isinstance(node.op, ast.And) else 'or'
        prec = PREC[type(node.op)]
        parts = [to_str(v, prec) for v in node.values]
        s = f' {op} '.join(parts)
        if prec < parent_prec:
            return f'( {s} )'
        return s

    # UnaryOp: only support Not here
    if isinstance(node, ast.UnaryOp) and isinstance(node.op, ast.Not):
        prec = PREC[type(node.op)]
        # 直接让子节点以 prec 作为 parent_prec 决定是否加括号（避免重复加括号）
        operand_str = to_str(node.operand, prec)
        return f'not {operand_str}'

    # Constant (Python 3.8+)
    if isinstance(node, ast.Constant):
        # 确保 True/False 以首字母大写形式输出
        val = node.value
        if val is True:
            return 'True'
        if val is False:
            return 'False'
        # 一般不会出现其他常量，但保底
        return str(val)

    # 兼容旧版本 (ast.NameConstant)
    if hasattr(ast, 'NameConstant') and isinstance(node, ast.NameConstant):
        if node.value is True:
            return 'True'
        if node.value is False:
            return 'False'
        return str(node.value)

    # 也兼容像直接写 True/False 作为 Name（极少见）
    if isinstance(node, ast.Name):
        return node.id

    # 比较/其他表达式：简单用 ast.unparse (若可用) 或回退到手动
    # 为了本题只需支持布尔表达式 True/False/and/or/not，所以其余类型抛错
    raise TypeError(f"Unsupported node type: {type(node)}")

def main():
    data = sys.stdin.read().strip()
    if not data:
        return
    # ast.parse 解析为 Expression
    tree = ast.parse(data, mode='eval')
    out = to_str(tree.body)
    print(out)

if __name__ == '__main__':
    main()

思路：只依赖运算符优先级，不建AST，一遍扫描、直接根据运算符优先级输出去除不必要括号的中缀表达式。这其实就是一个 Shunting Yard 的变体：仍然利用两个栈（操作数、操作符），但在“弹出并组合”时直接构造字符串，而不是树。关键是：在构造时根据优先级动态决定是否加括号。

✅ 最简洁、可通过、仅用优先级控制的版本

python

# T20576: printExp. 不建AST，直接基于运算符优先级一遍扫描输出最简括号中缀表达式

def priority(op):
    if op == 'not':
        return 3
    if op == 'and':
        return 2
    if op == 'or':
        return 1
    return 0

def is_op(x):
    return x in ('not', 'and', 'or')

expr = input().strip()
tokens = expr.replace('(', ' ( ').replace(')', ' ) ').split()

vals, ops = [], []

def apply():
    op = ops.pop()
    if op == 'not':
        a, pa = vals.pop()
        # 右操作数优先级 < 当前优先级 才加括号
        if pa < priority(op):
            a = f"( {a} )"
        vals.append((f"not {a}", priority(op)))
    else:
        b, pb = vals.pop()
        a, pa = vals.pop()
        # 左右侧根据优先级判断是否加括号
        if pa < priority(op):
            a = f"( {a} )"
        if pb <= priority(op):
            b = f"( {b} )"
        vals.append((f"{a} {op} {b}", priority(op)))

for t in tokens:
    if t == '(':
        ops.append(t)
    elif t == ')':
        while ops and ops[-1] != '(':
            apply()
        ops.pop()
    elif is_op(t):
        while ops and is_op(ops[-1]) and \
              ((t != 'not' and priority(ops[-1]) >= priority(t)) or
               (t == 'not' and priority(ops[-1]) > priority(t))):
            apply()
        ops.append(t)
    else:
        vals.append((t, 4))  # 操作数优先级最高（常数4）

while ops:
    apply()

print(vals[-1][0])

🔍 说明

两个栈：
- vals 存 (表达式字符串, 优先级)；
- ops 存操作符。
apply()：每次弹出一个操作符，根据优先级决定是否给子表达式加括号。
优先级规则：
```
not > and > or
```
not 是右结合（所以当后面的操作符优先级相等时不提前计算）。
括号控制逻辑：
- 左子式：若优先级 < 当前操作符，则加括号。
- 右子式：若优先级 ≤ 当前操作符，则加括号。
- 单目 not：若子式优先级 < 当前操作符，则加括号。

解读：

python

    elif is_op(t):
        while ops and is_op(ops[-1]) and \
              ((t != 'not' and priority(ops[-1]) >= priority(t)) or
               (t == 'not' and priority(ops[-1]) > priority(t))):
            apply()
        ops.append(t)

非常好的问题 👍 这几行是整个算法的核心关键，控制了操作符出栈的时机（即：当前要进来的运算符 t，是否要先让栈顶运算符计算完）。

我们来逐句完全拆解说明。

🎯 背景：Shunting Yard 的“运算符优先级处理规则”

Shunting Yard（调度场算法）：

当读到一个新的运算符时，要决定是否把栈顶运算符先弹出（并计算），还是暂时压栈等待以后处理。

逻辑：

如果栈顶运算符的优先级 ≥ 当前运算符，并且两者是左结合 → 弹出。
如果栈顶运算符的优先级 > 当前运算符，并且两者是右结合 → 弹出。
否则，直接把当前运算符压栈。

🧩 我们的代码片段

python

elif is_op(t):
    while ops and is_op(ops[-1]) and \
          ((t != 'not' and priority(ops[-1]) >= priority(t)) or
           (t == 'not' and priority(ops[-1]) > priority(t))):
        apply()
    ops.append(t)

🪄 一行一行解释

1️⃣ elif is_op(t):

如果当前 token 是运算符（not, and, or）。

2️⃣ while ops and is_op(ops[-1]) and ...

只要：

栈中还有运算符；
栈顶也是运算符（而不是括号）；
满足优先级出栈条件（下一步解释），就先执行 apply()。

也就是说，我们在进入新的运算符前，会清理掉该弹出的旧操作符。

3️⃣ 出栈条件（最重要）

python

((t != 'not' and priority(ops[-1]) >= priority(t)) or
 (t == 'not' and priority(ops[-1]) > priority(t)))

意思是：

当前运算符	栈顶运算符	何时弹出栈顶？
`and` / `or`（左结合）	优先级 ≥ 当前	弹出
`not`（右结合）	优先级 > 当前	弹出

解释：

左结合运算符（and, or） → 如果栈顶优先级相同或更高，就该先算；
右结合运算符（not） → 只在栈顶优先级更高时才弹出，避免例如 not not True 被提前计算成 (not not) True 这样的错误。

4️⃣ apply()

执行一次实际的计算（在我们这里，是拼接表达式字符串）。比如遇到：

not True or False

当处理 or 时，会先弹出 not（因为 not 优先级更高），执行 apply() 变为 "not True"。

5️⃣ ops.append(t)

最后把当前运算符压栈（因为还没执行完）。

🧠 举个例子理解整个 while 循环

输入：

not True or False

扫描到每个 token：

token	ops	vals	动作
`not`	[] → ['not']	[]	压入 not
`True`	['not']	[('True',4)]	压入值
`or`	['not'] → [] → ['or']	[('not True',3)]	因为栈顶 not 优先级高，先 apply 一次，然后压 or
`False`	['or']	[('not True',3), ('False',4)]	压入值

最终 apply 'or'： → 输出 not True or False

⚙️ 对比右结合例子

输入：

not not True

当处理第二个 not 时：

栈顶运算符也是 not
由于 not 是右结合
出栈条件是 priority(ops[-1]) > priority(t)（严格大于）
这时两者优先级相等 → 不会弹出

所以两个 not 会顺序压栈：

ops = ['not', 'not']

等遇到 True 后再按顺序 apply → 正确输出 not not True。如果我们用 >=，就会错误地提前算出 (not not) True。

✅ 小结表格

运算符	结合性	出栈条件	解释
`not`	右结合	栈顶优先级 > 当前	保证 `not not X` 不被提前执行
`and`, `or`	左结合	栈顶优先级 ≥ 当前	保证 `A and B and C` 从左往右算

20576: printExp ​

20576: printExp