具有功能支持的调车场算法 [英] Shunting-yard algorithm with function support
问题描述
我在互联网上找到了这种分流码算法的实现(带有函数支持的后缀中缀)
i found this implementation of the Shunting-yard algorithm over the internet (Infix to Postfix with function support)
infix_to_postfix(infix):
postfix = []
infix.add(')')
stack = []
stack.push('(')
for each token in infix:
if token is operand:
postfix.add(token)
if token is '[':
stack.push(token)
else if token is operator:
if stack is empty OR
stack[top] is '(' or stack[top] is '[':
stack.push(token)
else if (operator)token['precedence'] > stack[top]['precedence'] OR
( (operator)token['precedence'] == stack[top]['precedence'] AND
(operator)token['associativity') == 'RIGHT' ):
stack.push(token)
else
postfix.add(stack.pop())
stack.push(token)
else if token is '(':
stack.push(token)
else if token is ')':
while topToken = stack.pop() NOT '(':
postfix.add(topToken)
else if token is ']':
while True:
topToken = stack.pop()
postfix.add(topToken)
if topToken is '[':
break
else if token is ',':
while topToken = stack.peek() NOT '[':
postfix.add(topToken)
stack.pop()
stack.push(token)
我尝试将它移植到 C++，但我不明白我错在哪里这是我的代码:
i try to port it to c++ but I can't understand where I'm wrong that is my code:
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
using namespace std;
string magic(string& infix){
const string ops = "-+/*%^";
string postfix;
stringstream ss;
stack<char> s;
string token;
infix+=")";
s.push('(');
for(int c = 0; c<infix.length(); ++c){
for(int op = 0; op<ops.length(); ++op){
if(infix[c] == ops[op])
postfix+=infix[c];
}
for (int op = 0; op<ops.length(); ++op){
if(infix[c]=='['){
s.push(infix[c]);
}else if(infix[c] == ops[op]){
if(s.empty() || s.top()=='(' || s.top()=='[')
s.push(infix[c]);
else if(0){
// cose con le precedenze
}else{
s.pop();
postfix+=s.top();
s.push(infix[c]);
}
}else if(infix[c]=='('){
s.push(infix[c]);
}else if(infix[c]==')'){
while(s.top() != '('){
s.pop();
char topc = s.top();
postfix += topc;
}
}else if(infix[c]==']'){
while(true){
s.pop();
char topc = s.top();
postfix+= topc;
if(topc == '[')
break;
}
}else if(infix[c]==','){
while(s.top()!='['){
char topc = s.top();
postfix += topc;
s.pop();
}
s.push(infix[c]);
}
}
}
return postfix;
}
int main() {
string infix = "[ sin ( 2 , 5 ) ] + 3 ^ ( 4 * ( 5 * ( 6 - 1 ) ) )";
cout << "infix: " << infix << '\n';
cout << "postfix: " << magic(infix) << '\n';
return 0;
}
如果你不能用 C++ 开发，我有什么选择?是否有算法可以做更适合该问题的类似事情?欢迎提供所有代码答案，谢谢.
if you could not develop in C ++ what alternatives do I have? are there algorithms that do similar things more suited to the problem? all code answers are welcome, thanks.
推荐答案
翻译该答案中的代码时存在几个问题，包括答案本身中的一个相当明显的错误，即第二个 if (if token is '[') 应该是 else if.但是请注意，第一个if 中的条件是if token isoperand，但您的翻译大致是if token is operator.这两个问题肯定足以阻止您的代码按预期工作.
There are several problems with your translation of the code from that answer, including one fairly obvious error in the answer itself, which is that the second if (if token is '[') should be else if. But note that the condition in the first if is if token is operand, but your translation is, roughly, if token is operator. Those two issues are certainly enough to prevent your code from working as desired.
除此之外，阅读引用答案中的注释很重要，其中指出伪代码基于已经被标记化的输入；该代码不打算直接应用于输入.特别是，数字和变量名称应该是令牌流中的单个元素.另外，请参阅注释 3，其中解释了 [ 和 ] 的来源；它们不在输入流中，因此它们必须由标记生成器创建.
Beyond that, it's important to read the notes in the cited answer, which point out that the pseudocode is based on the input having already been tokenised; the code is not intended to be applied directly to the input. In particular, numbers and variable names should be single elements in the token stream. Also, see note 3 which explains where [ and ] come from; they are not in the input stream, so they must be created by the tokeniser.
当您尝试编写实现时，尝试了解算法的工作原理通常很有帮助，尤其是当您移植的是伪代码时.(伪代码最重要的一点是它不是代码，所以它永远不会被测试.即使是非常有经验的编码人员也不会注意到滑入伪代码的小错误是很常见的.如果有一种运行伪代码的方法，这样的错误会被立即检测到，但由于没有，在测试具体实现时会出现错误.简而言之，警告接收器.)
It's generally helpful to try to understand how an algorithm works when you're trying to write an implementation, particularly when what you are porting is pseudocode. (The most important thing about pseudocode is that it is not code, so it will never have been tested. It's quite common for even very experienced coders to not notice little errors which slipped into pseudocode. If there were a way of running the pseudocode, such errors would be detected immediately, but since there isn't, the errors will appear when a concrete implementation is tested. In short, caveat receptor.)
维基百科上的调车场算法有合理的解释.特别是，该维基百科页面上的伪代码处理函数调用，前提是函数的名称是已知的.
There's a reasonable explanation of the shunting-yard algorithm on Wikipedia. In particular, the pseudocode on that Wikipedia page handles function calls provided the names of the functions are known.
关于分流码的另一个讨论，包括关于如何在标记输入时识别函数调用和一元运算符(前缀和后缀)的注释，请参见 SO 上的这个答案，其中还包括伪代码.
For yet another discussion of shunting yard, including a note on how to recognise function calls and unary operators (prefix and postfix) while tokenising the input, see this answer on SO, which also includes pseudocode.
关于这三个 Shunting Yard 演示的一个有趣的事实是，它们每个都有自己的将函数调用转换为 postfix 的风格.您需要解决的具体问题是后缀函数调用是不明确的，除非您以某种方式知道使用了多少个参数.中缀调用中的括号使参数计数显式，但像后缀这样的无括号表示需要不同的机制.
An interesting fact about the three Shunting Yard presentations is that they each have their own style of translating function calls to postfix. The concrete problem you need to solve is that a postfix function call is ambiguous unless you somehow know how many arguments are used. The parentheses in the infix call make the argument count explicit, but a parenthesis-free representation like postfix needs a different mechanism.
使用逗号作为构建参数列表的二元运算符，就像在您尝试移植的代码中一样，是一种有趣的策略.但是，所提供的伪代码无法处理没有参数的函数.(此外，[ 标记也必须包含函数名称这一事实没有很好地解释.)
Using the comma as a binary operator which builds a parameter list, as in the code you are trying to port, is an interesting strategy. However, the pseudocode as presented cannot handle functions with no parameters. (Also, the fact that the [ token must also contain the function name is not very well explained.)
另一方面，维基百科代码依赖于识别用作函数的标识符.并且它要求每个这样的函数都具有众所周知的参数数量.这在计算器中没问题，其中函数通常仅限于 sin 和 digamma 之类的东西，但在通用编程语言中却有问题.
The Wikipedia code, on the other hand, relies on recognising the identifiers used as functions. And it requires each such function to have a well-known number of parameters. That's ok in a calculator, where functions are usually restricted to things like sin and digamma, but it's problematic in a general purpose programming language.
我的解决方案在后缀输出中插入了一个 CALL 操作符；正如注释所示，实际实现还应在 CALL 之前插入作为附加值提供的参数数量.但是，实施细节没有得到很好的解释.(对不起！)
My solution inserts a CALL operator into the postfix output; as a note indicates, a practical implementation should also insert the number of arguments supplied as an additional value just before CALL. The implementation details are not well-explained, though. (Sorry!)
这篇关于具有功能支持的调车场算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
