P10473 表达式计算4

SnowFlavour · 2025-09-05 21:07:13 · 题解

这份 Python 代码能够通过目前的所有 Hack。~~不过如果你想用 5 分钟水过去是不大可能的~~

实际上如果你乐意的话你也可以用和 C++ 完全相同的方式正常通过这道题目，但是我就是要用 eval()。

直接使用 eval() 大致会遇到这样几个问题：

括号不匹配。虽然大部分题解处理了这种情况，但是讨论区的 hack 显示他们对这个问题的处理都不算彻底。
运算符结合律。Python 自带的 ** 运算符是右结合的，也就是说，表达式 2**2**3 相当于 2**(2**3)。没有题解考虑到这种情况。
向零取整问题。这个问题就属于是纯语言特性了，而没有题解解决这个问题。

我们逐个分析这些问题。

括号匹配问题

实际上题目是有歧义的，不过我们可以考虑正解是怎么处理这种情况的。在栈中保存的 ( 会后进先出，那么如果 ( 剩下了，就一定是最开始的 ( 应该被舍弃。

而右括号会尝试和左括号匹配，如果不匹配的话就会跳过，那么就可以直接删除这个括号。

于是这两个问题就可以同时处理。然而一次处理之后，可能会再多出一些失配的括号，于是直接用一个循环来多次清理失配括号即可。（不过似乎也是能hack 的？）

    ls = list(s)
    dge = []
    tmp = ls.copy()
    while 1:
        dge = []
        for i in range(len(ls)):
            if ls[i] == ")" and (ls[:i + 1].count("(") < ls[:i + 1].count(")")):
                dge.append(i)
                ls[i] = "$"
        dge.reverse()
        for d in dge:
            del ls[d]
        while ls.count("(") > ls.count(")"): ls.remove("(")
        # print(ls)
        if ls == tmp:
            break

        tmp = ls.copy()

运算符结合律问题

这个问题应该是没什么简单的解决方法的。Python 中没有除了 ** 以外运算优先级高于 * 的二元运算符。

既然正着不行，我们可以考虑反过来，把所有的运算符都降级。也就是说，用 | 代表 +，用 ^ 代表 -（这个有点毛病，如果你把这个和指数放在一起的话需要考虑先后关系），依此类推。

请直接看代码：

def fh(x: int):
    if x > 0: return 1
    if x < 0: return -1
    if x == 0: return 0

class lfint(int):
    def __init__(self, x: int):
        super().__init__()
        self.x = x

    def __int__(self):
        return self.x

    def __xor__(self, value):
        return lfint(self.x - value.x)

    def __or__(self, value):
        return lfint(self.x + value.x)

    def __truediv__(self, value):
        return lfint(self.x ** value.x)

    def __lshift__(self, value):
        return lfint(self.x * value.x)

    def __rshift__(self, value):
        return lfint(abs(self.x) // abs(value.x) * fh(self.x) * fh(value.x))

    def __neg__(self):
        return lfint(-self.x)

这里我们实际上就是做了一步替换工作。很明显这个重载不能直接在 int 上进行，所以我们只能定义一个新的类。这就带来了下一个问题：怎么才能把输入的数转换成这个格式呢？

考虑使用正则表达式（需要用到 re 库）：

def hep(mat):
    val = mat.group("value")
    return "lfint(" + val + ")"

s = re.sub('(?P<value>\\d+)', hep, s)

这样的话我们就把每个数都套了一层转换，他就会按照正常的方式进行运算了。

向零取整问题

如果你认真阅读了上面的代码，你就会看到实际上这个问题已经被解决了——在运算的时候我们用正数计算，然后在把符号补充上就好了。

完整代码

行数已经到了大约 80 行（虽然我有一些空行），并没有比 C++ 的代码简单多少。实际上如果表达式是合法的，我们就不需要处理括号了，但是依然无法解决结合律问题。因此想偷懒应该是行不通滴……

import re
def fh(x: int):
    if x > 0: return 1
    if x < 0: return -1
    if x == 0: return 0
class lfint(int):
    def __init__(self, x: int):
        super().__init__()
        self.x = x

    def __int__(self):
        return self.x

    def __xor__(self, value):
        return lfint(self.x - value.x)

    def __or__(self, value):
        return lfint(self.x + value.x)

    def __truediv__(self, value):
        return lfint(self.x ** value.x)

    def __lshift__(self, value):
        return lfint(self.x * value.x)

    def __rshift__(self, value):
        return lfint(abs(self.x) // abs(value.x) * fh(self.x) * fh(value.x))

    def __neg__(self):
        return lfint(-self.x)

def hep(mat):
    val = mat.group("value")
    return "lfint(" + val + ")"

def prev(s: str):
    s = s.replace("+", "|").replace("*", "<<").replace("/", ">>").replace("^", "/").replace(")-", ")^")
    for i in range(1, len(s)): 
        if s[i] == "-" and s[i - 1].isdigit():
            s = s[:i] + "^" + s[i + 1:]

    return s
pf = prev(input())
# print(pf)
def fix(s: str):
    s = s.replace(" ", "")
    ls = list(s)
    dge = []
    tmp = ls.copy()
    while 1:
        dge = []
        for i in range(len(ls)):
            if ls[i] == ")" and (ls[:i + 1].count("(") < ls[:i + 1].count(")")):
                dge.append(i)
                ls[i] = "$"
        dge.reverse()
        for d in dge:
            del ls[d]
        while ls.count("(") > ls.count(")"): ls.remove("(")
        # print(ls)
        if ls == tmp:
            break

        tmp = ls.copy()

    # print("".join(ls), dge)
    s = "".join(ls)
    s = s.replace("a", "lfint(a)")
    return re.sub('(?P<value>\\d+)', hep, s)

pf = fix(pf)
# print(pf)
print(eval(pf))