表达式求值的一个问题
这个星期我做了一个表达式求值的程序（输入、输出和中间结果均只能是0～9）：
大概是这样的：输入一个中序表达式，用一个转换程序变为后序表达式，再对后序表达式求值，这两个子程序我都做出来了然后是主程序：我将转换出来的后序表达式存储再一个数组里，将数组头指针传递给求值程序，但就是这里出错了。希望高手指教！谢谢！！
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 2
typedef char SElemType;
typedef struct SqStack{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack *S){ /*初始化栈 */
(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW);
(*S).top = (*S).base;
(*S).stacksize = STACK_INIT_SIZE;
return OK;
}
char GetTop(SqStack S){ /*取栈顶元素 */
if(S.top == S.base)
return ERROR;
return *(S.top - 1);
}
Status Push(SqStack *S,SElemType e){ /*入栈 */
if((*S).top - (*S).base > = (*S).stacksize){
(*S).base = (SElemType *)realloc((*S).base,
((*S).stacksize + STACKINCREMENT) * sizeof
(SElemType));
if (!(*S).base)
exit (OVERFLOW);
(*S).top = (*S).base + (*S).stacksize;
(*S).stacksize += STACKINCREMENT;
}
*((*S).top)++ = e;
return OK;
}
char Pop(SqStack *S,SElemType *e){ /*出栈 */
if((*S).top == (*S).base)
return ERROR;
*e = * --(*S).top;
return *e;
}
Status In(char c){ /*判断是否为运算符 */
int i;
int j = 0;
char OP[] = { '+ ', '- ', '* ', '/ ', '( ', ') ', '# '};
for (i = 0; i <= 6; i++){
if (c == OP[i])
j++;
}
if (j)
return TRUE;
else
return FALSE;
}
char Precede(char opnd1, char opnd2){ /*运算符优先级 */
int i, j;
char guanxi[7][7]={ '> ', '> ', ' < ', ' < ', ' < ', '> ', '> ',
'> ', '> ', ' < ', ' < ', ' < ', '> ', '> ',
'> ', '> ', '> ', '> ', ' < ', '> ', '> ',
'> ', '> ', '> ', '> ', ' < ', '> ', '> ',
' < ', ' < ', ' < ', ' < ', ' < ', '= ', ' ',
'> ', '> ', '> ', '> ', ' ', '> ', '> ',
' < ', ' < ', ' < ', ' < ', ' < ', ' ', '= '};
switch(opnd1){
case '+ ': i = 0;break;
case '- ': i = 1;break;
case '* ': i = 2;break;
case '/ ': i = 3;break;
case '( ': i = 4;break;
case ') ': i = 5;break;
case '# ': i = 6;break;
default: exit(ERROR);
};
switch(opnd2){
case '+ ': j = 0;break;
case '- ': j = 1;break;
case '* ': j = 2;break;
case '/ ': j = 3;break;
case '( ': j = 4;break;
case ') ': j = 5;break;
case '# ': j = 6;break;
default: exit(ERROR);
};
return guanxi[i][j];
}
int Operate(int opnd1, SElemType theta, int opnd2){ /*运算 */
int c;
switch(theta)
{
case '+ ':c = opnd1 + opnd2;
break;
case '- ':c = opnd1 - opnd2;
break;
case '* ':c = opnd1 * opnd2;
break;
case '/ ':c = opnd1 / opnd2;
}
return c;
}
char *zhuanhuan(){ /*中序表达式转换为后序表达式 */
SqStack OPTR;
SElemType a, b, c, x, theta;
char exp[30];
int i = 0;
InitStack(&OPTR);
Push(&OPTR, '# ');
c = getchar();
while (c != '# ' || GetTop(OPTR) != '# '){
if (!In(c)){
exp[i] = c;
i++;
c = getchar();
}
else
switch(Precede(GetTop(OPTR),c)){
case ' < ': Push(&OPTR, c);
c = getchar();
break;
case '> ': if(c == ') '){
while (GetTop(OPTR) != '( ' ){
Pop (&OPTR, &a);
exp[i] = a;
i++;
}
Pop(&OPTR, &x);
c = getchar();
}
else{
Pop(&OPTR, &b);
exp[i] = b;
i++;
}
break;
}
}
exp[i] = '\0 ';
printf( "%s\n ",exp);
return exp;
}
char qiuzhi(char *exp){ /*后序表达式求值 */
SqStack OPND;
int i = 0;
SElemType a, b;
int j;
SElemType c = exp[i];
InitStack(&OPND);
while(c){
if(!In(c)){
Push(&OPND, c - '0 ');
c = exp[++i];
}
else{
Pop(&OPND, &a);
Pop(&OPND, &b);
j = Operate(b, c, a);
Push(&OPND, j);
c = exp[++i];
}
}
return GetTop(OPND);
}
void main(){ /*主程序 */
char *ch = zhuanhuan();
char i;
i = qiuzhi(ch);
printf( "%d\n ", i);
}
[解决办法]
数据结构辅导：
http://sysop.com.cn/system4864,1.html
这两个连接中讲述的都是楼主你所做的工作，
【推荐这个连接http://sysop.com.cn/system4864,1.html】
看看这个思想、算法，以及参看一下其中的代码吧 ～～
[解决办法]
zhuanhuan()函数中，exp为局部变量，生存期为函数期限，调用完后当然就没有了，当然不能被返回了，你可以尝试用全局变量或引用类型
[解决办法]
多调试， 单步跟踪， 添加watch查看表达式值
呵呵 编程不仅要会编程序， 调试也是非常重要的
[解决办法]
在zhuanhuan() 函数中,exp为局部变量,该内存地址在返回主函数之后被释放掉了..
把exp的定义改为: static char exp[30]; 试试.
[解决办法]
楼主你出错的原因应该是在zhuanhuan这个函数中,你的返回值是一个栈内的变量,是一个数组名.
这是不行的,因为当这个函数结束之后,这个exp也就生命期结束了,所以返回的只是一堆无用的垃圾而已.你要把它改成在堆上建立的数组才行,另外在主函数接收之后,要记得释放内存,我改了一下,如下:
char *zhuanhuan(){ /*中序表达式转换为后序表达式 */
SqStack OPTR;
SElemType a, b, c, x, theta;
// char exp[30];
char *exp=(char*)malloc(30); //在这里改为堆内存
int i = 0;
InitStack(&OPTR);
Push(&OPTR, '# ');
c = getchar();
while (c != '# ' || GetTop(OPTR) != '# '){
if (!In(c)){
exp[i] = c;
i++;
c = getchar();
}
else
switch(Precede(GetTop(OPTR),c)){
case ' < ': Push(&OPTR, c);
c = getchar();
break;
case '> ': if(c == ') '){
while (GetTop(OPTR) != '( ' ){
Pop (&OPTR, &a);
exp[i] = a;
i++;
}
Pop(&OPTR, &x);
c = getchar();
}
else{
Pop(&OPTR, &b);
exp[i] = b;
i++;
}
break;
}
}
exp[i] = '\0 ';
printf( "%s\n ",exp);
return exp;
}
void main(){ /*主程序 */
char *ch = zhuanhuan();
char i;
i = qiuzhi(ch);
printf( "%d\n ", i);
free(ch); //这里记得free掉内存就行了
}
[解决办法]
返回函数内的局部变量(本例中的exp数组),也就是栈内存是一个很大的错误,因为栈内存的生命期是在函数内,函数结束它的生命就结束了
堆内存是可以返回的(改成exp=(char*)malloc(30)之后),因为它的生命期是程序级的,在整个程序运行期间一直存在
