Question

C语言用栈编写求表达式的值

C语言用栈编写求表达式的值，我这样写编译通过，但一运行就直接提示停止。求大神纠错。

#include<stdio.h>
#include<stdlib.h>
char n[8]="+-*/()#";
char m[8][8]={">><<<>>",">><<<>>",">>>><>>",">>>><>>","<<<<<= ",">>>> >>","<<<<< ="};
typedef struct Snode_N{
int data;
struct Snode_N *next;
}Snode_N;
typedef struct Stack_N{
struct Snode_N *top;
int len;
}Stack_N;
void init_N(Stack_N *S)
{
S->top=NULL;
S->len=0;
}
void push_N(Stack_N *S,char e)
{
struct Snode_N *p=(Snode_N*)malloc(sizeof(Snode_N));
p->data=e-'0';
p->next=S->top;
S->top=p;
S->len++;
}
int pop_N(Stack_N *S)
{
struct Snode_N *p;
int e;
p=S->top;
e=p->data;
S->top=p->next;
free(p);
S->len--;
return e;
}
//-----------------------------------//
typedef struct Snode_T{
char data;
struct Snode_T *next;
}Snode_T;
typedef struct Stack_T{
struct Snode_T *top;
int len;
}Stack_T;
void init_T(Stack_T *S)
{
S->top=NULL;
S->len=0;
}
void push_T(Stack_T *S,char e)
{
struct Snode_T *p;
p=(Snode_T*)malloc(sizeof(Snode_T));
p->data=e;
p->next=S->top;
S->top=p;
S->len++;
}
char pop_T(Stack_T *S)
{
struct Snode_T *p;
char e;
p=S->top;
e=p->data;
S->top=p->next;
free(p);
S->len--;
return e;
}
//----------------------------------------//
int In(char c)
{
int i;
for (i=0;i<=6;i++)
if (n[i]==c) return 1;
return 0;
}
int ope(int a,char t,int b)
{
switch(t)
{
case'+':return (a+b);
case'-':return (a-b);
case'*':return (a*b);
case'/':return (a/b);
}
}
char Cmp(char c1,char c2)
{
int i=0,j=0;
while (i<7&&n[i]!=c1)
i++;
while (j<7&&n[j]!=c2)
j++;
return(m[i][j]);
}
int main()
{
Stack_N *OPN;
Stack_T *OPT;
char c,t;
int a,b;
init_N(OPN);
init_T(OPT);
push_T(OPT,'#');
c=getchar();
while (c!='#'||pop_T(OPT)!='#')
{
if (In(c)==0)
{
push_N(OPN,c);
c=getchar();
}
else
{
switch(Cmp(pop_T(OPT),c))
{
case'<':
push_T(OPT,c);
c=getchar();
break;
case'=':
pop_T(OPT);
c=getchar();
break;
case'>':
t=pop_T(OPT);
a=pop_N(OPN);
b=pop_N(OPN);
push_N(OPN,ope(b,t,a));
break;
}
}
}
printf("%d\n",pop_N(OPN));
}

Answer 1

//表达式输入完了之后直接回车，就出结果了，跟平时输入字符串一样。

/**********************************************
算术表达式求值的算符优先级算法
利用栈来实现括号匹配和表达式求值
算法的详细说明，请查看清华大学出版社《数据结构》，严蔚敏&吴伟民著，3.3节
***********************************************/
#include<stdlib.h>
#include<stdio.h>
#include<ctype.h>
//存储空间初始分配量
#define STACK_INIT_SIZE 100
//存储空间分配增量
#define STACKINCREMENT 10
#define OK 0
#define ERROR 127

//定义一个顺序栈
typedef struct
{
int*base; //在栈构造之前和销毁之后，base的值为NULL
int*top; //栈顶指针
int stacksize; //当前已分配的存储空间,以元素为单位
}SqStack;
int InitStack(SqStack*S)
{
//构造一个空栈
S->base=(int*)malloc(STACK_INIT_SIZE*sizeof(SqStack));
if(NULL==S->base)
{ //内存分配失败
return ERROR ;
}
S->top=S->base ;
S->stacksize=STACK_INIT_SIZE ;

return OK ;
}
char GetTop(SqStack*S,char*element)
{
//若栈不空，取栈顶元素,用element返回
if(S->base==S->top)
{
return ERROR ;
}
*element=*(S->top-1);

return*element ;
}
int Push(SqStack*S,int element)
{
//插入元素element为新的栈顶元素
if((S->top-S->base)>S->stacksize)
{
//栈满，追加空间
S->base=(int*)realloc(S->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SqStack));
if(NULL==S->base)
{
return ERROR ;
}
S->top=S->base+S->stacksize ;
S->stacksize+=STACKINCREMENT ;
}
*S->top++=element ;

return OK ;
}
int Pop(SqStack*S,int*element)
{
//若栈不为空，则删除栈顶元素，用element返回其值
if(S->top==S->base)
{
return ERROR ;
}
*element=*(--S->top);

return OK ;
}
int PopOPTR(SqStack*S,char*element)
{
if(S->top==S->base)
{
return ERROR ;
}
*element=*(--S->top);

return OK ;
}
//判断字符c是否在集合OP中
int InOP(char c,char OP[7])
{
for(int i=0;i<7;i++)
{
if(c==OP[i])
{
return OK ;
}
}

return ERROR ;
}
//判断运算符的优先级
int Compare(int a,int b)
{
if('+'==a)
{
switch(b)
{
case '+' :
return '>';
case '-' :
return '>' ;
case '*' :
return '<' ;
case '/' :
return '<' ;
case '(' :
return '<' ;
case ')' :
return '>' ;
case '\n' :
return '>' ;
}
}
if('-'==a)
{
switch(b)
{
case '+' :
return '>' ;
case '-' :
return '>' ;
case '*' :
return '<' ;
case '/' :
return '<' ;
case '(' :
return '<' ;
case ')' :
return '>' ;
case '\n' :
return '>' ;
}
}

if('*'==a)
{
switch(b)
{
case '+' :
return '>' ;
case '-' :
return '>' ;
case '*' :
return '>' ;
case '/' :
return '>' ;
case '(' :
return '<' ;
case ')' :
return '>' ;
case '\n' :
return '>' ;
}
}

if('/'==a)
{
switch(b)
{
case '+' :
return '>' ;
case '-' :
return '>' ;
case '*' :
return '>' ;
case '/' :
return '>' ;
case '(' :
return '<' ;
case ')' :
return '>' ;
case '\n' :
return '>' ;
}
}

if('('==a)
{
switch(b)
{
case '+' :
return '<' ;
case '-' :
return '<' ;
case '*' :
return '<' ;
case '/' :
return '<' ;
case '(' :
return '<' ;
case ')' :
return '=' ;
}
}

if(')'==a)
{
switch(b)
{
case '+' :
return '>' ;
case '-' :
return '>' ;
case '*' :
return '>' ;
case '/' :
return '>' ;
case ')' :
return '>' ;
case '\n' :
return '>' ;
}
}

if('\n'==a)
{
switch(b)
{
case '+' :
return '<' ;
case '-' :
return '<' ;
case '*' :
return '<' ;
case '/' :
return '<' ;
case '(' :
return '<' ;
case '\n' :
return '=' ;
}
}
return ERROR ;
}

//简单计算
int Calculate(int left,char oper,int right)
{
int result=0 ;
switch(oper)
{
case '+' :
result=left+right ;
break ;
case '-' :
result=left-right ;
break ;
case '*' :
result=left*right ;
break ;
case '/' :
result=left/right ;
break ;
}

return result ;
}

/**********************************************
算术表达式求值的算符优先级算法，设OPTR和OPND分别为运算符栈和运算数栈
OP为运算符集合
**********************************************/
int main()
{
SqStack OPTR,OPND ;
int element=0 ;
char OPTR_element ;
int leftNum,rightNum ;
char input ;
//获取输入
char OP[7]={'+','-','*','/','(',')','\n'};

InitStack(&OPTR);
Push(&OPTR,'\n');
InitStack(&OPND);
printf("请输入表达式\n");
input=getchar();
while('\n'!=input||'\n'!=GetTop(&OPTR,&OPTR_element))
{
int temp=0 ;
if(isdigit(input))
{
//如果是数字
ungetc(input,stdin);
//返回给输入流
scanf("%d",&temp);
Push(&OPND,temp);
//数字就进OPND栈
input=getchar();
continue ;
}

if(OK==InOP(input,OP))
{
GetTop(&OPTR,&OPTR_element);
switch(Compare(OPTR_element,input))
{
case '<' :
//栈顶元素优先级低
Push(&OPTR,input);
//运算符进OPTR栈
input=getchar();
break ;
case '=' :
//脱括号
PopOPTR(&OPTR,&OPTR_element);
input=getchar();
break ;
case '>' :
//退栈，并将运算结果入栈
PopOPTR(&OPTR,&OPTR_element);
Pop(&OPND,&rightNum);
Pop(&OPND,&leftNum);
Push(&OPND,Calculate(leftNum,OPTR_element,rightNum));
break ;
default :
printf("表达式括号不匹配\n");
return ERROR ;
}//switch
}//if

else
{
printf("表达式内有未知字符,即将退出\n");
return ERROR ;
}
}//while

int value ;
Pop(&OPND,&value);
printf("结果 = %d\n",value);

return OK ;
}//end

Answer 2

你先这样改一下。

MAIN函数中定义的时候：

Stack_N OPN, *pOPN = &OPN;
	Stack_T OPT, *pOPT = &OPT;

然后全部用这两个指针。

你那是内存错误，因为你根本就没有一个栈的实体，却一直用指针操作它。。。

追问

改过以后还是错啊。。。

追答

我的main函数

int main()
{
    Stack_N OPN, *pOPN;
    Stack_T OPT, *pOPT;
    char c,t;
    int a,b;

    pOPN = &OPN;
    pOPT = &OPT;
    init_N(pOPN);
    init_T(pOPT);
    push_T(pOPT,'#');
    c=getchar();
    while (c!='#'||pop_T(pOPT)!='#')
    {
        if (In(c)==0)
        {
            push_N(pOPN,c);
            c=getchar(); 
        }
        else 
        {
            switch(Cmp(pop_T(pOPT),c))
            {
            case'<':
                push_T(pOPT,c);
                c=getchar();
                break;
            case'=':
                pop_T(pOPT);
                c=getchar();
                break;
            case'>':
                t=pop_T(pOPT);
                a=pop_N(pOPN);
                b=pop_N(pOPN);
                push_N(pOPN,ope(b,t,a));
                break;
            }
        }
    }
    printf("%d\n",pop_N(pOPN));
}

你出什么问题了，如何输入的？

Answer 3

栈越界了吧

追问

不是很懂。。。能具体点吗。