26572: 多余的括号
http://cs101.openjudge.cn/practice/26572/
小明总是记不清四则运算的优先级关系，为了保险起见，他总是在算式中加上许多冗余的括号，但层层嵌套的括号可苦了批改作业的老师。现在想请你编写一个程序，在不改变算式运算顺序的前提下，删除其中多余的括号。
为了简单起见，我们只考虑加法和乘法两种运算，其中乘法优先级高于加法。题目保证给出的算式是合法的，且所有出现的运算数都是非负整数，不含正负号。
输入是若干行只含有非负整数、加号、乘号和括号的四则运算表达式。对于每一行输入，你的程序需要输出一行结果，即删去表达式中所有冗余括号后得到的简化表达式。
输入
(1+11) ((1+2))+3*(4+5)
输出
1+11 1+2+3*(4+5)
样例输入
(1+11)
((1+2))+3*(4+5)
1+(2+3)样例输出
1+11
1+2+3*(4+5)
1+(2+3)来源: lxp
2025/6/4 修正过测试数据。正确方法应该是中缀转后缀，后缀再转中缀表达式（同时满足题面要求：不改变算式运算顺序）。
基于 中缀表达式转后缀表达式（也叫逆波兰表示法，Reverse Polish Notation，RPN）的思想，并在后缀表达式的基础上再转回中缀表达式，同时去除冗余的括号。下面代码也可以 AC。
python
import re
def infix_to_postfix(tokens):
"""
中缀（tokens）→ 后缀：
- 使用栈存运算符，根据优先级（+：1，*：2）和左结合性来出栈与入栈。
- 数字直接输出到 postfixList，遇到 '(' 入栈，遇到 ')' 则依次弹出运算符直到遇到 '('。
"""
op_stack = []
postfix = []
prec = {"+": 1, "*": 2}
for tk in tokens:
if tk.isdigit():
# 数字（包括多位）直接放到后缀列表
postfix.append(tk)
elif tk == "(":
op_stack.append(tk)
elif tk == ")":
# 右括号时，把栈顶运算符都弹出直到遇到左括号
while op_stack and op_stack[-1] != "(":
postfix.append(op_stack.pop())
op_stack.pop() # 弹出 '('
else:
# 运算符：比较优先级，优先级低（或相等）的运算符先出栈
while (op_stack and op_stack[-1] != "("
and prec[tk] <= prec[op_stack[-1]]):
postfix.append(op_stack.pop())
op_stack.append(tk)
# 最后把栈里剩余的运算符都弹出
while op_stack:
postfix.append(op_stack.pop())
return postfix
def postfix_to_infix(postfix):
"""
后缀 → 中缀（去冗余括号）：
- 每次遇到数字就把 (字符串, “自身优先级”) 入栈。这里设计：
数字的“自身优先级”设为 3，
'+' 的优先级设为 1，
'*' 的优先级设为 2。
- 每次遇到 '+' 或 '*'：
从栈顶弹出右操作数 (右子表达式, right_prec)，
再弹出左操作数 (左子表达式, left_prec)。
设当前运算符 op 的优先级为 prec_op（'+'→1，'*'→2）。
1) 左子表达式需要加括号的条件是：left_prec < prec_op
（也就是子表达式的根运算符优先级更低，一定要加括号）。
2) 右子表达式需要加括号的条件是：
- 子表达式的根运算符优先级更低： right_prec < prec_op
（相当于 “1 * (2+3)” 这种情况，子表达式是加法、优先级 < 乘法，必须加括号），
- 或者 子表达式的根运算符优先级等于当前运算符且 “当前运算符是左结合”：
right_prec == prec_op
（例如 “a + (b + c)” 里，右边如果也是 ‘+’，没有括号会变成 “a + b + c”
（即 (a+b)+c），这改变了原先“先算 b+c 再加 a”的顺序，必须保留）。
这样就能保证：在重建中缀字符串时，只加必要的括号，不会破坏原始运算顺序。
"""
stack = []
for tk in postfix:
if tk.isdigit():
# 数字本身优先级设为 3
stack.append((tk, 3))
else:
# tk 是 '+' 或 '*'
right_str, right_prec = stack.pop()
left_str, left_prec = stack.pop()
prec_op = 2 if tk == "*" else 1
# 左子表达式加括号的条件：left_prec < prec_op
if left_prec < prec_op:
left_str = f"({left_str})"
# 右子表达式加括号的条件：
# right_prec < prec_op 或
# right_prec == prec_op （因为 + 和 * 均为左结合，
# 同级右侧子表达式必须加括号）
if right_prec < prec_op or right_prec == prec_op:
right_str = f"({right_str})"
merged = f"{left_str}{tk}{right_str}"
stack.append((merged, prec_op))
return stack.pop()[0]
def simplify_expression(expr):
# 用正则把多位数字和运算符/括号拆开
tokens = re.findall(r'\d+|[()+*]', expr)
postfix = infix_to_postfix(tokens)
return postfix_to_infix(postfix)
# 主流程：读每一行、输出简化后的结果
if __name__ == "__main__":
import sys
for line in sys.stdin:
line = line.strip()
if not line:
continue
print(simplify_expression(line))python
import sys
# 运算符优先级和结合性（左结合 = 'L'，右结合 = 'R'）
PRECEDENCE = {
'+': (1, 'L'),
'-': (1, 'L'),
'*': (2, 'L'),
'/': (2, 'L'),
'NEG': (3, 'R'), # 一元负号
}
class Node:
def __init__(self, value, left=None, right=None):
self.value = value # 运算符或数值
self.left = left
self.right = right
def is_leaf(self):
return self.left is None and self.right is None
def tokenize(expr):
tokens = []
i = 0
while i < len(expr):
if expr[i].isspace():
i += 1
elif expr[i] in '+-*/()':
tokens.append(expr[i])
i += 1
elif expr[i].isdigit():
num = ''
while i < len(expr) and expr[i].isdigit():
num += expr[i]
i += 1
tokens.append(num)
else:
raise ValueError(f"Invalid character: {expr[i]}")
return tokens
def parse_expr(tokens):
i = 0
def parse_primary():
nonlocal i
if tokens[i] == '-':
# 一元负号
i += 1
return Node('NEG', right=parse_primary())
elif tokens[i] == '(':
i += 1
node = parse_add_sub()
i += 1 # skip ')'
return node
else:
val = tokens[i]
i += 1
return Node(val)
def parse_unary():
return parse_primary()
def parse_mul_div():
nonlocal i
node = parse_unary()
while i < len(tokens) and tokens[i] in ('*', '/'):
op = tokens[i]
i += 1
node = Node(op, node, parse_unary())
return node
def parse_add_sub():
nonlocal i
node = parse_mul_div()
while i < len(tokens) and tokens[i] in ('+', '-'):
op = tokens[i]
i += 1
node = Node(op, node, parse_mul_div())
return node
return parse_add_sub()
def to_string(node, parent_op=None, is_right=False):
if node.is_leaf():
return node.value
if node.value == 'NEG':
expr = to_string(node.right, 'NEG', True)
if not node.right.is_leaf() and PRECEDENCE.get(node.right.value, (0,))[0] < PRECEDENCE['NEG'][0]:
expr = f'({expr})'
return f'-{expr}'
left_expr = to_string(node.left, node.value, False) if node.left else ''
right_expr = to_string(node.right, node.value, True)
def need_paren(child, parent, is_right_child):
if child.is_leaf():
return False
child_prec, _ = PRECEDENCE.get(child.value, (0, 'L'))
parent_prec, parent_assoc = PRECEDENCE.get(parent, (0, 'L'))
if child_prec < parent_prec:
return True
if child_prec == parent_prec:
if parent_assoc == 'L' and is_right_child:
return True
if parent_assoc == 'R' and not is_right_child:
return True
return False
if need_paren(node.left, node.value, False):
left_expr = f'({left_expr})'
if need_paren(node.right, node.value, True):
right_expr = f'({right_expr})'
return f'{left_expr}{node.value}{right_expr}'
def simplify_expression(expr):
tokens = tokenize(expr)
ast = parse_expr(tokens)
return to_string(ast)
if __name__ == '__main__':
for line in sys.stdin:
line = line.strip()
if line:
print(simplify_expression(line))