问题标签 [shunting-yard]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
0 回答
729 浏览

c++ - 修改调车场算法以处理分数和变量

我正在使用 Jesse Brown 的调车场算法实现的修改版本。我正在尝试修改变量系统以基本上执行符号数学,而不是为变量分配双精度值。例如,我不想简单地声明 pi = 3.14,而是希望它只在解决方案中包含 pi。所以 1+2+pi 将导致 3+pi。

代码如下。我刚刚开始弄乱它,并没有做很多。有没有人有任何想法?

0 投票
1 回答
165 浏览

java - 调车场算法问题

所以这是我的代码:

我不断收到奇怪的错误,一个告诉我嵌套 if 语句中的 if(operators.peek().equals... 位返回 EmptyStackException。我在尝试将弹出的数字 (endNumber) 强制转换为返回时遇到另一个错误它。我在将其转换为双精度时遇到了问题。

如果有人会看到这个并告诉我问题是什么以及解决问题的任何可能方法,那就太好了,因为我真的不明白为什么它会给我这些错误。

我知道删除 divert[i].equals("+")/("-") 消除了第一个错误的问题,但这对我正在做的事情不太有利。

0 投票
2 回答
406 浏览

php - 布尔表达式:多个中缀字符串的后缀

给定以下(中缀)表达式:

我想创建以下 4 个中缀符号:

所以,基本上,我想摆脱所有的 OR。

我已经有了第一个表达式的后缀符号,所以我目前正在尝试处理它以获得所需的符号。然而,这种特殊情况会引起麻烦。

(为了说明的目的,这个查询的后缀表示法是:)

有谁知道实现这一目标的算法?

0 投票
1 回答
218 浏览

java - 理解表达式解析为二叉树的绝对值?

我正在为表达式编写解析器,其中包括标记)、(、|、*、+、-、/、变量和常量。

到目前为止,我的代码适用于 *,/,-,+,(,),但我不知道如何处理绝对值。

用括号,我以(开始,以)结束,这很简单,但是我如何确定哪个“|” 是开场,哪个是闭场?

对于解析,我使用两个堆栈和分流场算法(或者至少我理解和编写它的方式)。

0 投票
1 回答
1743 浏览

algorithm - 用于立即评估的调车场算法

通常,评估中缀数学表达式的程序使用Shutting Yard 算法的一些变体,首先将表达式转换为逆波兰表示法,然后评估逆波兰表示法以获得单个最终值。

我的问题是,是否有一些众所周知的算法绕过 INFIX -> RPN 步骤,并使用某种递归下降解析来评估初始中缀表达式?

据推测,在编写编译器或解析器来翻译 INFIX -> RPN 时它可能很有用。RPN 是一种表达式(AST)的“编译形式”,可以更容易地由计算机使用简单的输出堆栈进行评估。但是,如果您只是简单地编写将中缀表达式立即转换为数字输出值的代码,那么缓存中间 RPN 表单可能没有任何用处。

那么,是否有任何众所周知的算法来解析中缀表达式而不首先转换为 RPN?还是转换为 RPN 通常比任何其他方法更有效?

0 投票
2 回答
374 浏览

php - Apply distributive law on AST (or RPN) => disjunctive normal form

I have expressions like the following:

Allowed operators are OR and AND, expressions can be nested using parenthesis. I already managed to tokenize this string and to convert it to an abstract syntax tree (AST) using the Shunting Yard algorithm, implemented in PHP 5.3. The above expression results in the following:

When traversing this tree I want to output the final combinations of numbers a user can choose from. In the given representation this is not possible. What I need is actually the form, after the distributive law was applied:

I concluded, that the only nodes that are allowed to be &-operator nodes, are the last ones that carry the leafs. All others have to be |-operator nodes.

How to convert an arbitrary AST with the grammar explained above to one that represents all final permutations? Is it better to apply the distributive law on the tokens of the infix representation? Is it easier to work with the RPN representation instead of the tree?

Please also note, that there are more difficult examples possible like:

Which I'd like to result in:

For another (more complicated) example just switch left sub tree and right sub tree or add another &-node in place of 1003 => 1003 1009 &

What I already tried: Googling a lot, traversing the tree pre and post order, trying to find an algorithm with no success.

I am grateful for any hints and pointers into the right direction.

0 投票
1 回答
805 浏览

java - 调车场算法实现中优先级值的含义

我正在编写一个计算器类来学习 Java。到目前为止,它可以处理简单的函数,例如2+2,2^2等,但我正在尝试实现 Shutting Yard 算法,以便它可以处理更复杂的表达式。

我是数据结构的新手,没有指南就无法编写这样的代码,因此经过研究,我在网上找到了几个示例,并正在关注其中的一个。其他网站,如果您有兴趣:1 , 2。我选择了第一个链接站点,因为我对它的理解是三个中最好的。

但我不明白作者在这里做什么:

我知道这与运算符的优先级有关,但我不确定这些数字来自哪里。有人可以澄清一下吗?

另外,我的计算器有一个作者没有包含的指数方法。如果我要包含它,它是否会比除了流结束/EOS 和默认选项之外的所有内容具有更高的优先级?

(如果你有更好的调车场算法实现,请提出建议!)

0 投票
1 回答
2742 浏览

java - 使用Shunting Yard的计算器-收到postfix后如何进行

我正在编写一个计算器来学习 Java。我最近编写了一个与这个非常相似的 Shutting Yard 算法。我的算法和链接算法之间的唯一区别是我还包括一个指数运算符。以下是更改:

和:

其他一切都是一样的。

但是,我对 Java 和数据结构非常陌生,我不确定:

  1. 如何在我的 Calc 类中实现 Shutting Yard 算法。
  2. 如何开始处理算法提供的后缀。

对于这两个问题或您看到的其他问题的任何建议或示例,将不胜感激。

下面是我的计算器的原始代码框架,它只能处理简单的功能,例如2+2. 评论是我开始实施 Shutting Yard 算法的想法,但我不确定我是否走在正确的轨道上。注释将替换它们上方/下方的某些行。我不确定这段代码中有多少仍然可用。

谢谢!

0 投票
1 回答
47 浏览

c++ - 在类中实例化变量

我正忙于调车场算法。如果你有这样的表达:

该类不知道变量名称和值是什么。所以我在类中有一个函数,instantianteVariable(char name, int value),调用:

如何用现在已知的变量替换表达式中的未知变量?x 和 y 可以是任何字符,因此我无法创建名称为 x 和 y 的类成员。

0 投票
1 回答
1294 浏览

math - Shunting Yard Algorithm with Variables

I'm currently working on a modified version of the Shunting Yard Algorithm that would work with variables, but I cant figure out how to get it to work. For example, I would want the algorithm to re-write 2 * (2x + 5) - 5 to 4x + 5. Any ideas / links to already implemented algorithms that does this already?