我在互联网上发现了调车场算法的这种实现(支持功能的Infix到Postfix(
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++开发，我有什么替代方案？有没有做类似事情的算法更适合这个问题？欢迎所有代码回答，谢谢。
从该答案翻译代码时有几个问题，包括答案本身的一个相当明显的错误，即第二个if(if token is '['(应该是else if。但请注意，第一个if中的条件是if token is operand，但您的翻译大致是if token is operator。这两个问题肯定足以阻止您的代码按预期工作。
除此之外，阅读引用答案中的注释很重要，这些注释指出伪代码是基于已经标记的输入的；该代码不打算直接应用于输入。特别是，数字和变量名应该是令牌流中的单个元素。另外，请参阅注释3，其中解释了[和]的来源；它们不在输入流中，因此它们必须由标记生成器创建。
当您试图编写实现时，尤其是当您移植的是伪代码时，尝试了解算法是如何工作的通常是有帮助的。(关于伪代码，最重要的是它不是代码，所以它永远不会经过测试。即使是非常有经验的程序员也很常见，不会注意到伪代码中出现的小错误。如果有运行伪代码的方法，这些错误会立即被检测到，但由于没有，所以在测试具体实现时会出现错误。简而言之，警告受体。(
维基百科上对调车场算法有一个合理的解释。特别是，维基百科页面上的伪代码处理函数调用，前提是函数的名称是已知的。
关于调车场的另一个讨论，包括关于如何在标记输入时识别函数调用和一元运算符(前缀和后缀(的说明，请参阅SO上的答案，其中也包括伪代码。
关于三个ShuttingYard演示的一个有趣的事实是，它们都有自己的风格，可以将函数调用转换为后缀。您需要解决的具体问题是，除非您知道使用了多少个参数，否则后缀函数调用是不明确的。中缀调用中的括号使参数计数显式，但像后缀这样的无括号表示需要不同的机制。
使用逗号作为构建参数列表的二进制运算符，就像在您试图移植的代码中一样，是一种有趣的策略。然而，所提供的伪代码无法处理没有参数的函数。(此外，[令牌还必须包含函数名这一事实并没有得到很好的解释。(
另一方面，维基百科的代码依赖于识别用作函数的标识符。它要求每个这样的函数都有一个众所周知的参数数量。这在计算器中是可以的，函数通常被限制在sin和digamma之类的东西上，但在通用编程语言中是有问题的。
我的解决方案在后缀输出中插入一个CALL运算符；如注释所示，实际实现还应在CALL之前插入作为附加值提供的参数数。不过，实现细节没有得到很好的解释。(对不起！(