用栈实现表达式求值的程序,运行结果是不对的
自己写的,但会出错,想好长时间了,望高手解决
#include <stdio.h>
#include <conio.h>
struct nuStack
{
int array[50];
int top;
};
struct opStack
{
char array[50];
int top;
};
int precede(char a,char b) /*符号优先级 1表示> 2表示= 3表示 < 4表示无效 */
{
if((a== '( '&&b== ') ')||(a== '# '&&b== '# '))
{
return 2;
}
else
{
if((a== '( '&&b== '# ')||(a== ') '&&b== '( ')||(a== '# '&&b== ') '))
{
return 4;
}
else
{
if(a== '( ')
{
return 3;
}
if(a== '# ')
{
return 3;
}
if(a== ') ')
{
return 1;
}
if(b== '# ')
{
return 1;
}
if(b== '( ')
{
return 3;
}
if(b== ') ')
{
return 1;
}
if(a== '* '||a== '/ ')
{
return 1;
}
if((a== '+ '||a== '- ')&&(b== '* '||b== '/ '))
{
return 3;
}
else
{
return 1;
}
}
}
}
void InitopStack(struct opStack *stack)
{
stack-> top=0;
}
void InitnuStack(struct nuStack *stack)
{
stack-> top=0;
}
int GetnuTop(struct nuStack *stack)
{
return stack-> array[stack-> top-1];
}
char GetopTop(struct opStack *stack)
{
return stack-> array[stack-> top-1];
}
void pushnu(struct nuStack *stack,int a)
{
stack-> array[stack-> top]=a;
stack-> top=stack-> top+1;
}
void pushop(struct opStack *stack,char a)
{
stack-> array[stack-> top]=a;
stack-> top=stack-> top+1;
}
int popnu(struct nuStack *stack)
{
stack-> top=stack-> top-1;
return stack-> array[stack-> top];
}
char popop(struct opStack *stack)
{
stack-> top=stack-> top-1;
return stack-> array[stack-> top];
}
int operate(char a,int b,int c)
{
if(a== '+ ')
{
return b+c;
}
if(a== '- ')
{
return b-c;
}
if(a== '* ')
{
return b*c;
}
if(a== '/ ')
{
return b/c;
}
}
main()
{
struct opStack *OPTR;
struct nuStack *OPND;
char c[100],op,get;
int a,n1,n2,result;
int i=0,j;
OPTR=(struct opStack*)malloc(sizeof(struct opStack));
OPND=(struct nuStack*)malloc(sizeof(struct nuStack));
InitopStack(OPTR);
InitnuStack(OPND);
pushop(OPTR, '# ');
printf( "Please input the EvaluateExpression: ");
get=getchar();
while(get!= '# ')
{
c[i]=get;
i++;
get=getchar();
}
c[i]= '# ';
i++;
for(j=0;j <i;j++)
{
if(c[j]> = '0 '&&c[j] <= '9 ')
{
a=c[j]- '0 ';
pushnu(OPND,a);
}
else
{
if(precede(GetopTop(OPTR),c[j])==3)
{
pushop(OPTR,c[j]);
}
else
{
if(precede(GetopTop(OPTR),c[j])==2)
{
popop(OPTR);
}
else
{
if(precede(GetopTop(OPTR),c[j])==1)
{
op=popop(OPTR);
n2=popnu(OPND);
n1=popnu(OPND);
pushnu(OPND,operate(op,n1,n2));
}
}
}
}
}
result=GetnuTop(OPND);
printf( "The answer is:%d ",result);
getch();
}
[解决办法]
运算对象栈dst 和运算符栈ost。逐个读入单词，其中：
——遇运算对象，直接压入dst
——遇运算符o，与ost 栈顶o ' 比较。o ' 优先级不低于o 时弹出o '，从dst 弹出运算对象，计算结果压入dst。反复至栈顶运算符优先级低于o 时将运算符o 压入ost
——遇左括号，直接进栈ost
——遇右括号，逐个弹出运算符，从dst 弹出运算对象，计算并将结果压入dst，直至把对应左括号弹出
——遇表达式结束，逐个弹出运算符并进行计算，直至处理完全部运算符
——若ost 只有一个元素则完成并输出，否则表达式有错。
里面还有一些别的算法上的错误，比如入栈的运算符不够。
我给你代码里加了一些测试输出，你自己分析（格式我用indent调整了）：
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct nuStack
{
int array[50];
int top;
};
struct opStack
{
char array[50];
int top;
};
int
precede (char a, char b) /*符号优先级 1表示> 2表示= 3表示 < 4表示无效 */
{
if ((a == '( ' && b == ') ') || (a == '# ' && b == '# '))
{
return 2;
}
else
{
if ((a == '( ' && b == '# ') || (a == ') ' && b == '( ')
|| (a == '# ' && b == ') '))
{
return 4;
}
else /* 你干嘛不用switch语句？？？ */
{
if (a == '( ')
{
return 3;
}
if (a == '# ')
{
return 3;
}
if (a == ') ')
{
return 1;
}
if (b == '# ')
{
return 1;
}
if (b == '( ')
{
return 3;
}
if (b == ') ')
{
return 1;
}
if (a == '* ' || a == '/ ')
{
return 1;
}
if ((a == '+ ' || a == '- ') && (b == '* ' || b == '/ '))
{
return 3;
}
else
{
return 1;
}
}
}
}
void
InitopStack (struct opStack *stack)
{
stack-> top = 0;
}
void
InitnuStack (struct nuStack *stack)
{
stack-> top = 0;
}
int
GetnuTop (struct nuStack *stack)
{
return stack-> array[stack-> top - 1];
}
char
GetopTop (struct opStack *stack)
{
return stack-> array[stack-> top - 1];
}
void
pushnu (struct nuStack *stack, int a)
{
stack-> array[stack-> top] = a;
stack-> top = stack-> top + 1;
}
void
pushop (struct opStack *stack, char a)
{
stack-> array[stack-> top] = a;
stack-> top = stack-> top + 1;
}
int
popnu (struct nuStack *stack)
{
stack-> top = stack-> top - 1;
return stack-> array[stack-> top];
}
char
popop (struct opStack *stack)
{
stack-> top = stack-> top - 1;
return stack-> array[stack-> top];
}
int
operate (char a, int b, int c)
{
if (a == '+ ')
{
return b + c;
}
else if (a == '- ')
{
return b - c;
}
else if (a == '* ')
{
return b * c;
}
else if (a == '/ ')
{
return b / c;
}
else
{
printf ( "--An error occured when calculating '%d %c %d '.\n ", b, a, c);
return -99999999;
}
}
main ()
{
struct opStack *OPTR;
struct nuStack *OPND;
char c[100], op, get;
int a, n1, n2, result;
int i = 0, j;
OPTR = (struct opStack *) malloc (sizeof (struct opStack));
OPND = (struct nuStack *) malloc (sizeof (struct nuStack));
InitopStack (OPTR);
InitnuStack (OPND);
pushop (OPTR, '# ');
printf ( "Please input the EvaluateExpression:\n ");
get = getchar ();
while (get != '# ')
{
c[i] = get;
i++;
get = getchar ();
}
c[i] = '# ';
i++;
for (j = 0; j < i; j++)
{
if (c[j] > = '0 ' && c[j] <= '9 ')
{
a = c[j] - '0 ';
pushnu (OPND, a);
printf ( "--push number %d.\n ", a);
}
else if (precede (GetopTop (OPTR), c[j]) == 3)
{
printf ( "--push operator %c.\n ", c[j]);
pushop (OPTR, c[j]);
}
else if (precede (GetopTop (OPTR), c[j]) == 2)
{
printf ( "--get operator %c. pop operator stack.\n ", c[j]);
popop (OPTR);
}
else if (precede (GetopTop (OPTR), c[j]) == 1)
{
op = popop (OPTR);
n2 = popnu (OPND);
n1 = popnu (OPND);
pushnu (OPND, operate (op, n1, n2));
printf
( "--get operator %c. calculate '%d %c %d '. push the result %d.\n ",
c[j], n1, op, n2, operate (op, n1, n2));
}
}
if (OPND-> top != 1)
printf ( "STACK ERROR!\n ");
result = GetnuTop (OPND);
printf ( "The answer is:%d\n ", result);
getch ();
}
