java - java 中具有右结合性的表达式求值

Question

我正在尝试解决一个问题，其中我必须解决一个给定的表达式，该表达式由同一字符串中的一个或多个初始化组成，没有运算符优先级(尽管带有括号内的子表达式)。所有运算符都有右优先级，因此我必须从右到左对其进行评估。我很困惑如何继续解决给定的问题。详细问题在这里给出:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=108

Answer 1

我会给你一些尝试的想法:

首先，您需要递归地计算括号内的值。您想要从最嵌套到最少嵌套执行括号，因此请使用与括号内没有 ) 匹配的正则表达式。将计算结果子串到括号表达式占用的字符串部分中。

如果没有括号，那么现在您需要计算运算符。问题之所以需要正确的优先级，是为了迫使你思考如何回答它——你不能只读取字符串并进行计算。您必须考虑整个字符串，然后开始进行计算，这意味着存储一些描述它的结构。您可以使用多种策略来执行此操作，例如:

- 您可以使用扫描仪或正则表达式对字符串进行标记 - 不断尝试查看字符串中的下一项是否是数字或它是哪个运算符，并推送它是什么类型的标记及其值到一个 list 上。然后，您可以使用某种 case/switch 结构从右到左评估列表，以确定每个运算符要执行的操作(或者每个运算符与其对数字执行的操作相关联)。 = 本身会寻址变量名称键到值的映射，并将值插入该变量的键下，然后返回(放入列表中)它产生的值，因此可以使用它进行另一项任务。看来-可以通过其右侧是否有空格来判断是减法还是负数。

- 您可以对整个字符串使用正则表达式，而不是标记化。但标记化更加稳健。我尝试构建一个基于一遍又一遍地将正则表达式应用于整个字符串的计算器，但要使所有规则正确非常困难，我不推荐它。

我之前写过一个这样的表达式求值计算器，所以如果您遇到具体问题，可以向我提问。