java - 运算符优先算法

Question

我目前正在为自定义编程语言编写编译器。编译器将每个 单个运算符或调用转换为以下形式的对象

Call : Value
{
  Value instance
  String name
  Value[] arguments
}

例如，表达式 3 + 4 (= 3.+(4)) 变为

Call : Value
{
  instance = Value(3)
  name = "+"
  arguments = [ Value(4) ]
}

表达式 3 + 4 * 5 将被解析器评估为 3.+(4).*(5)。

Call : Value
{
  instance = Call
             {
               instance = Value(3)
               name = "+"
               arguments = Value(4)
             }
  name = "*"
  arguments = [ Value(5) ]
}

我知道有一个函数可以创建此结构中的调用列表并按运算符优先级对它们进行排序，结果如下所示:

[ 3.+(4).*(5), 3.+(4) ](以上形式)

我现在需要的是一种对它们进行排序的算法，以便第一个表达式是 3.+(4.*(5))。这个问题是上面的结果可以有任何长度。我当前的实现(依赖于它是 2 个或更少的中缀运算符)是这样的:

(go through all elements)
{
  current.arguments = [ prev ]
  prev.instance = current.arguments[0]
}

我知道运算符优先级通常是通过 BNF 文件中用于生成解析器的特殊结构来实现的，但由于我使用的是自定义解析器，它始终会从左到右计算这个值，所以我无法使用此类解决方案。

Answer 1

一种常见的解决方案是有时称为“调车场”的算法，它使用运算符堆栈。

• 以最低优先级将标记压入堆栈
• 获得小学
• 找个接线员
• 如果优先级较低或没有更多运算符，弹出堆栈并生成代码
• 将运算符压入栈中
• 循环直到剩下标记为止

我相信您会找到更好的解释，但我就是这样做的。