>我需要一个函数来获取中缀字符串（如"3 + 4 * 9"），并将其转换为后缀（如"4 9 * 3 +"）。
我让它工作，直到你在括号内加上括号。我整天都在研究它，无法弄清楚我做错了什么 - 也许有新鲜头脑的人能看到它吗？我觉得我真的很接近！
谢谢！代码如下：
string ExpressionManager::infixToPostfix(string infixExpression)
{
cout << "itop Testing : " << infixExpression << endl;
string posnums = "0123456789";
string posops = "+-*/%(){}[]";
string onlyops = "+-/%*";
string space = " ";
string openbra = "([{";
string closebra = ")]}";
stack <string> nums;
stack <string> ops;
string output = "";
//check to make sure expression is valid
if (!(isBalanced(infixExpression)))
{
cout << "Infix Expression isn't balanced!" << endl;
return "invalid";
}
for (int i=0; i<infixExpression.size(); i++)
{
if ((posnums.find(infixExpression[i])!=string::npos) || (posops.find(infixExpression[i])!=string::npos) || (space.find(infixExpression[i])!=string::npos))
{}
else
{
cout << "Invalid character " << infixExpression[i] << " found." << endl;
return "invalid";
}
}
int numcount = 0;
int opcount = 0;
//Numbers vs. Operators
for (int i = 0; i < infixExpression.size(); i++)
{
if (posnums.find(infixExpression[i]) != -1)
{
while(infixExpression[i] != ' ')
{
if (i == (infixExpression.size()-1))
break;
i++;
}
numcount++;
}
if (onlyops.find(infixExpression[i]) != -1)
{
opcount++;
}
}
if (opcount == (numcount - 1))
{
}
else
{
cout << "Bad operators to numbers ratio!" << endl;
return "invalid";
}
//Get rid of proceeding whitespaces.
int safety = 0;
int net = infixExpression.size();
while (infixExpression[0] == ' ')
{
infixExpression.erase(0,1);
safety++;
if (safety>=net)
break;
}
//cout << "At this point, it is " << postfixExpression << endl;
//the fun part! Set up stacks
for (int i =0; i< infixExpression.size(); i++)
{
cout << "It gets hung up on character " << infixExpression[i] << endl;
if(openbra.find(infixExpression[i]) != -1)
{
string word = "";
word += infixExpression[i];
ops.push(word);
cout << "Pushing onto stack: " << word << endl;
}
else if(closebra.find(infixExpression[i]) != -1)
{
cout << "contents of remaining ops stack: "<< endl;
stack <string> temp;
temp = ops;
for (int j = 0; j < temp.size(); j++)
{
cout << "t" << temp.top() << endl;
temp.pop();
}
while (openbra.find(ops.top()) == -1)
{
output += " " + ops.top();
cout << "Pushing from stack: " << ops.top() << endl;
ops.pop();
}
cout << "Pushing from stack: " << ops.top() << endl;
ops.pop();
}
else if (posnums.find(infixExpression[i]) != -1)
{
string word = "";
while (infixExpression[i] != ' ')
{
word += infixExpression[i];
i++;
if (i== infixExpression.size())
break;
}
output += " " + word;
}
else if (onlyops.find(infixExpression[i]) != -1)
{
if (ops.size() == 0)
{
string word = "";
word += infixExpression[i];
ops.push(word);
}
else
{
int o1p = 0;
int o2p = 0;
if ((infixExpression[i] == '+') || (infixExpression[i] == '-'))
o1p = 0;
else
o1p = 1;
if ((ops.top() == "+") || (ops.top() == "-"))
o2p = 0;
else
o2p = 1;
while ((ops.size() > 0) && (o1p <= o2p))
{
output += " " + ops.top();
cout << "(odd) Pushing from stack: " << ops.top() << endl;
if ((ops.top() == "+") || (ops.top() == "-"))
o2p = 0;
else
o2p = 1;
if (ops.size() > 0)
{
ops.pop();
}
else
{
break;
}
}
string word = "";
word += infixExpression[i];
ops.push(word);
}
}
}
while (output[0] == ' ')
{
output.erase(0,1);
}
return output;
}
我个人认为你必须更努力地研究分流场算法
因为你说输出就像"4 9 * 3 +"，但我读到的关于算法和堆栈操作的内容，应该是（比如"9 4 * 3 +"）
重要的问题是，在对数字和运算符进行分类后，从运算符堆栈中全部弹出，并根据要弹出的运算符的设置条件推送到数字堆栈中
我的建议是你直接去相关的维基页面，描述
- 调车场算法
- 反向波兰语表示法
我已经在Java和C++中实现了调车场算法，发现Wiki页面非常出色，是一个很好的帮助来源。 它们足够详细，使您能够使用您喜欢的任何编程语言逐步实现算法。
另一个建议：相当熟悉堆栈和队列的实际用法，因为它们在这些算法中无处不在。
请参阅此博客文章，了解上述调车场算法的一些C++和 Java 实现。
如果您希望包括其他数学运算符（sin，cos，log等）以及更复杂的表达式和子表达式，它还包含另一个部分（正在进行中）。
这是解决方案的（最新版本）。在某些步骤中，它使用 Dijkstra 的调车场算法（如果我们以正确的方式遍历它，则在traverse()成员函数的末尾output_成员包含 input_ 表达式的反向抛光符号形式）。