我正在尝试创建一个程序，使用结构节点在C++中使用堆栈数据结构将中缀表达式转换为后缀表达式。 相关函数用于从堆栈中推送，弹出值。 程序会编译，但在输出窗口中输入一个中缀表达式示例'a+b'后，会出现一个运行时错误。 下面是完整的代码。
#include <iostream>
#include<cstring>
using namespace std;
struct Node{
char data;
struct Node * next;
}*top=NULL;
void Push(char x)
{ struct Node* p=new Node;
if(p==NULL)
cout<<"\nStack Overflow";
else{
p->data=x;
p->next=top;
top=p;
}
}
char Pop(){
int x=-1;
struct Node * p;
if(top==NULL)
cout<<"\nStack is Empty";
else{
p=top;
x=p->data;
top = top->next;
delete p;
}
return x;
}
int isEmpty(){
return top?0:1;
}
int Pre(char ch){
if(top==NULL)
return 0;
else if(ch == '-' || ch == '+')
return 1;
else if(ch == '*' || ch == '/')
return 2;
else
return 3;
}
char * InToPost(char *infix){
char *postfix = new char[strlen(infix)+1];
int i=0,j=0;
while(infix[i]!='\0')
{
if(Pre(infix[i]>Pre(top->data)))
Push(infix[i++]);
else{
while(Pre(infix[i])<=Pre(top->data))
postfix[j++]= Pop();
}
}
while(!isEmpty())
postfix[j++]=Pop();
postfix[j] = '\0';
return postfix;
}
int main(){
char *infix = new char[30];
cin>>infix;
cout<<InToPost(infix);
}
错误的原因可能是您没有递增while循环的else部分中的“i”的值。 这就是导致无限循环的原因。 另外，您可能错误地将括号放置在while循环的if条件中。 但是，即使你做了这些改变，它也不会给你正确的结果。 我认为你在尝试一个错误的方法。 每个字母表都应该直接推入“后缀”数组，而不是堆栈中。 我们只需要检查运算符的前缀，而不是字母。 您可以尝试实现以下代码。 我没有使用堆栈的链接实现，而是直接使用STL中的堆栈，但您可以根据需要进行所需的更改，这里我将附加字符“A”推入堆栈，以便检查堆栈中是否没有运算符。
int prec(char ch){
if(ch == '^')
return 3;
if(ch == '*' or ch == '/')
return 2;
if(ch == '+' or ch == '-')
return 1;
return -1;
}
string infixToPostfix(string x)
{
stack<char> s;
s.push('A');
string ans;
int n = x.length();
for(int i = 0 ; i < n; i++){
if((x[i] >= 'a' and x[i] <= 'z') or (x[i] >= 'A' and x[i] <= 'Z'))
ans += x[i];
else if(x[i] == '(')
s.push(x[i]);
else if(x[i] == ')'){
while(s.top() != 'A' and s.top() != '('){
ans += s.top();
s.pop();
}
if(s.top() == '('){
s.pop();
}
}
else{
while(s.top() != 'A' and prec(x[i]) <= prec(s.top())){
ans += s.top();
s.pop();
}
s.push(x[i]);
}
}
while(s.top() != 'A'){
ans += s.top();
s.pop();
}
return ans;
}
试试这个。 应该管用！ 它也适用于包含偏执狂的表达式，如a+b*(c+d)+(f+g)
我已经修改了你的代码。
1）在->char Pop（）中声明char x=-1，而不是int x=-1
2）按照下面的代码更改您的pre功能
int Pre（char ch）{
if(ch == '-' || ch == '+') return 1;
if(ch == '*' || ch == '/') return 2;
else return 0;
}
3）在InToPost（）内更改while循环
while（中缀[i]！='\0')
{
if(Pre(infix[i])==0) // if char is operand then push into postfix array
postfix[j++] = infix[i++]; // you were not using j++ with postfix array
else{
if(isEmpty()==1) // if stack is empty then push into Stack
Push(infix[i++]);
else
{
if(Pre(infix[i])>=Pre(top->data)) // If coming operator has same or less predence then push into Stack
Push(infix[i++]);
else{
while(Pre(infix[i])<=Pre(top->data))
postfix[j++]= Pop();
}
}
}
}
