具有函数支持的调车场算法

Question

我在互联网上找到了调车场算法的这个实现 (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++，但我不明白我哪里错了那是我的代码：

    #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++ 开发，我有什么选择？是否有算法可以做更适合该问题的类似事情？欢迎所有代码答案，谢谢。

Answer 1

您对该答案的代码的翻译有几个问题，包括答案本身的一个相当明显的错误，即第二个 if (if token is '[') 应该是 else if。但是请注意，第一个 if 中的条件是 if token is operand，但您的翻译大致是 if token is operator。这两个问题肯定足以阻止您的代码按预期工作。

除此之外，阅读引用答案中的注释很重要，它指出伪代码基于已经被标记化的输入；该代码不打算直接应用于输入。特别是，数字和变量名应该是令牌流中的单个元素。另外，请参阅注释 3，它解释了 [ 和 ] 的来源；它们不在输入流中，因此它们必须由标记器创建。

在尝试编写实现时尝试了解算法的工作原理通常很有帮助，尤其是当您移植的是伪代码时。（关于伪代码最重要的一点是它不是代码，所以它永远不会被测试。即使是非常有经验的编码人员也很容易注意到伪代码中的小错误。如果有一种方法运行伪代码，这种错误会立即被检测到，但由于没有，所以在测试具体实现时会出现错误。简而言之，caveat receptor.)

the shunting-yard algorithm on Wikipedia 有一个合理的解释。特别是，如果函数名称已知，该维基百科页面上的伪代码将处理函数调用。

关于调车场的另一个讨论，包括关于如何在标记化输入时识别函数调用和一元运算符（前缀和后缀）的注释，请参阅 this answer on SO，其中还包括伪代码。

关于调车场的三个演示文稿的一个有趣事实是，它们每个都有自己的将函数调用转换为后缀的风格。您需要解决的具体问题是后缀函数调用是不明确的，除非您以某种方式知道使用了多少参数。中缀调用中的括号使参数显式计数，但像后缀这样的无括号表示需要不同的机制。

使用逗号作为构建参数列表的二元运算符，就像在您尝试移植的代码中一样，是一种有趣的策略。但是，所提供的伪代码无法处理没有参数的函数。（此外，[ 标记还必须包含函数名称这一事实没有得到很好的解释。）

另一方面，维基百科代码依赖于识别用作函数的标识符。并且它要求每个这样的函数都具有众所周知的参数数量。这在计算器中没问题，其中函数通常仅限于 sin 和 digamma 之类的东西，但在通用编程语言中这是有问题的。

我的解决方案是在后缀输出中插入一个 CALL 运算符；如注释所示，实际实现还应在 CALL 之前插入作为附加值提供的参数数量。但是，实施细节没有得到很好的解释。（抱歉！）

具有函数支持的调车场算法

Shunting-yard algorithm with function support

c++

pseudocode

infix-notation

shunting-yard