#include <iostream>
#define maxSize 100
using namespace std;
int getpriority(char a)
{
if(a=='+'||a=='-')
return 0;
else
return 1;
}
void infixtopostfix(char infix[],char s2[],int &top2)
{
char s1[maxSize];
int top1=-1;
int i=0;
while(infix[i]!='\0')
{
if('0'<=infix[i] && infix[i]<='9')
s2[++top2]=infix[i++];
if(infix[i]=='+' || infix[i]=='-' ||infix[i]=='*' || infix[i]=='/')
{
if(top1==-1 || s1[top1]=='(' || getpriority(s1[top1])<getpriority(infix[i]))
s1[++top1]=infix[i++];
else
{
s2[top2]=s1[top1--];
++i;
}
}
if(infix[i]==')')
{
while(s1[top1]!='(')
s2[++top2]=s1[top1--];
--top1;
++i;
}
}
while(top1!=-1)
s2[++top2]=s1[top1--];
}
int main()
{
char infix[maxSize]={'(','a','+','b',')','*','c','\0'};
char result[maxSize];
int top2=-1;
infixtopostfix(infix,result,top2);
for(int i=0;i<8;++i)
cout<<result[i]<<" ";
return 0;
}
用递归写起来简单些。
加了跟踪打印语句,找到原因是没有处理开括号。(加了限制循环次数以便看到开始的输出。)
#include <iostream>
#define maxSize 100
using namespace std;
int getpriority(char a)
{
if(a=='+'||a=='-')
return 0;
else
return 1;
}
void infixtopostfix(char infix[],char s2[],int &top2)
{
char s1[maxSize];
int top1=-1;
int i=0;
int loop = 0;
while(infix[i]!='\0')
{
if (++loop > 10)
break;
cout << "start while: infix[" << i << "] = " << infix[i] << endl;
if('0'<=infix[i] && infix[i]<='9') {
s2[++top2]=infix[i++];
cout << "s2[++top2]=infix[i++]: s2[" << top2 << "] = " << infix[i-1] << endl;
}
cout << "To check op: infix[" << i << "] = " << infix[i] << endl;
if(infix[i]=='+' || infix[i]=='-' ||infix[i]=='*' || infix[i]=='/')
{
if(top1==-1 || s1[top1]=='(' || getpriority(s1[top1])<getpriority(infix[i])) {
s1[++top1]=infix[i++];
cout << "s1[++top1]=infix[i++]: s1[" << top1 << "] = " << infix[i-1] << endl;
}
else
{
s2[top2]=s1[top1--];
++i;
}
}
cout << "To check ): infix[" << i << "] = " << infix[i] << endl;
if(infix[i]==')')
{
while(s1[top1]!='('){
s2[++top2]=s1[top1--];
cout << "while not (: s2[" << top2 << "] = " << s1[top1+1] << endl;
}
--top1;
++i;
cout << "if ): top1 = " << top1 << ", i = " << i << endl;
}
}
cout << "last while: top1 = " << top1 << endl;
while(top1!=-1) {
s2[++top2]=s1[top1--];
cout << "last while: s2[" << top2 << "] = " << s1[top1+1] << endl;
}
}
int main()
{
char infix[maxSize]={'(','a','+','b',')','*','c','\0'};
char result[maxSize];
int top2=-1;
infixtopostfix(infix,result,top2);
for(int i=0;i<8;++i)
cout<<result[i]<<" ";
return 0;
}
// Output
To check ): infix[0] = (
start while: infix[0] = (
To check op: infix[0] = (
To check ): infix[0] = (
start while: infix[0] = (
To check op: infix[0] = (
To check ): infix[0] = (
start while: infix[0] = (
To check op: infix[0] = (
To check ): infix[0] = (
start while: infix[0] = (
To check op: infix[0] = (
To check ): infix[0] = (
start while: infix[0] = (
To check op: infix[0] = (
To check ): infix[0] = (
start while: infix[0] = (
To check op: infix[0] = (
To check ): infix[0] = (
start while: infix[0] = (
To check op: infix[0] = (
To check ): infix[0] = (
start while: infix[0] = (
To check op: infix[0] = (
To check ): infix[0] = (