我正在将仅包含函数调用和整数的表达式从中缀表示法转换为后缀表示法(仅字母、数字、逗号、括号,没有空格)。
例如,add(add(1,2),add(3,4))
到 1 2 add 3 4 add add
。
输入表达式长 22 个字符,输出为 19 个字符,短了 3 个字符。
sqrt(add(5,11))
到 5 11 add sqrt
。
输入表达式长 15 个字符,输出长 13 个字符,短 2 个字符。
后缀表示法总是会缩短等于函数数量的字符数量吗?
最佳答案
中缀需要更多语法吗?这是一个有趣的问题。但是,您给出的示例是前缀表示法,而不是中缀。简短的回答是:是的,在某些情况下中缀可能需要更多语法(例如消除运算符优先级的歧义)。
我相信计算必要的标记可能比计算字符更有意义。让我们看看会发生什么。
在您的前缀示例中,通过将左括号移至运算符左侧并用空格替换逗号,我们得到了 Lisp:(+ (+ 1 2) (+ 3 4))
和(sqrt (+ 5 11))
.
然后我们可以简单地反转所有内容并使用后缀表示法(但不会减少标记或字符数):((1 2 +) (3 4 +) +)
和((5 11 +) sqrt)
.
鉴于数量是固定的(+
是二进制,sqrt
是一元),我们可以明确地删除括号并得到:1 2 + 3 4 + +
和5 11 + sqrt
。事实上,对于固定数量运算符,在任何情况下都不需要括号。它们从一开始就不是有意义的、必要的标记。
但是中缀需要更多语法吗?好吧,由于运算符优先级,这个 2 × (3 + 4)
与 2 × 3 + 4
不同。括号对于指示中缀表示法的优先级是必需的。无论您选择什么语法,您都必须添加一些东西来消除歧义。然而,在后缀(或前缀)中,这两个表达式可以用相等的标记计数明确表示(并且始终少于中缀): 2 3 × 4 +
和2 3 4 + ×
或3 4 + 2 ×
.
我希望这能回答您的问题!
关于character - 当中缀表示法中的数字已知时,后缀表示法中的字符数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24061434/