我如何解决一个简单的字符串算术表达式，如5-2*10？

Question

由于某些原因，我在尝试这样做时遇到了很多麻烦。我有一个类，它要求我使用递归计算一个复杂的Java表达式，比如(3 + 53*2-4)。我想我有一个关于如何处理它的想法，但我似乎想不出如何首先解决一些非常简单的问题-比如

5-2*10

我不知道该怎么做。它们不允许您导入任何外部脚本，也不允许您将其转换为后缀表达式。

我不期望任何人给我写代码，但如果有人能把我送到正确的方向，或者给我一点伪代码，我会非常感激--我花了大约两个小时试图理解如何使用字符串标记器和其他东西来解决它，但我总是遇到不知道如何解决的障碍。提前谢谢你！

Answer 1

您可以连续减少子表达式(所谓的"redexes")，直到不能再减少为止。

这种内部表达式的替换可以使用正则表达式来完成：

1. "(\d+)(*/)(-?\d+)"
2. "(\d+)(+-)(-?\d+)"
3. "[(-?\d+)]"
4. ...

循环中的循环。请参见Pattern、Matcher、find。

由于这似乎是家庭作业，我将进一步的挑战留给您。

负数可能有点困难，可以尝试一元减号运算符。

Answer 2

回到大学的时候，我也不得不这么做。

我采用的方法是parse expressions using recursive descent。本文很好地概述了解析器应该如何标记您的输入，然后您可以继续对其进行评估。这里你必须意识到的关键是，让你的解析器成为top-down会让你的生活变得更容易，因为如果你从解析树的底部开始，从单个字符开始，然后使用规则将字符连接成更大的令牌，这将需要你维护一个堆栈，并且变得过于复杂。与此相反，因为您知道您所做的都是逻辑操作，所以您可以首先假设您的表达式与您的产生式规则匹配，然后您可以继续查看此假设的内部逻辑含义。

如果您选择构建自顶向下解析器或自底向上解析器，这些Brief Notes on Parsing实际上很好地解释了实现的不同之处。但是，根据解析器需要处理的表达式的复杂程度，您可能会使用choose to implement a bottom-up parser，因为尽管它们很复杂，但自下而上的解析算法比自上而下的算法更强大。

我构建的解析器是用OCaml编写的，而函数式编程被证明是这个用例的一个很好的解决方案。

如果你有任何问题请告诉我!

Answer 3

您需要实现一个表达式分析器。

下面是它通常是如何完成的摘要。您可以交替使用以下步骤，从左到右扫描字符串。每个方法使用一些文本并返回一个整数值。

• 一种计算整数的方法:它以数字开头。收集所有连续的数字并将其转换为一个值。
• 评估因子的方法:如果它以数字开头，则评估一个整数。如果它以'(‘开头，则计算一个表达式。如果不是，则是错误的。
• 评估term的方法:评估因子。当下一个字符是*或/时，跳过它，计算一个附加因子，然后将先前的值乘以新值或除以新值。
• 评估的方法:评估一项。当下一个字符是+或-时，跳过它，计算一个附加项，并将新值与前一个值相加或相减。
• 计算表达式的方法:它以'(‘开头。跳过它并计算一个总和。如果下一个字符是')'，则跳过它。如果不是，则是错误。