Question

数据结构 表达式求值

谁能帮我看看下面的程序有那些错误啊！ 帮我该一下啦！ 谢谢哦！
#include <stdio.h>
#define maxsize 10

typedef struct
{
char data[maxsize];
int top;
}SqStack;

void InitStack(SqStack *sq)
{
sq->top=0;
}

/*数据进栈*/
void Push(SqStack *sq,char m)
{
if(sq->top==maxsize-1)
{
printf("Full!\n");
}
else
{
sq->top++;
sq->data[sq->top]=m;
}
}

/*数据退栈*/
void Pop(SqStack *sq,char *m)
{
if(sq->top==0)
{
printf("Empty!\n");
}
else
{
*m=sq->data[sq->top];
sq->top--;

}
}

/*取运算符*/
void GetTop(SqStack *sq,char *x)
{
if(sq->top==0)
printf("Empty!/n");
else
{
*x=sq->data[sq->top];
}
}

/* 判断两符号的优先关系 */
char Precede(char t1,char t2)
{
char f;
switch(t2)
{
case '+':
case '-':if(t1=='('||t1=='#')
f='<';
else
f='>';
break;
case '*':
case '/':if(t1=='*'||t1=='/'||t1==')')
f='>';
else
f='<';
break;
case '(':if(t1==')')
{
printf("ERROR1\n");
break;
}
else
f='<';
break;
case ')':switch(t1)
{
case '(':f='=';
break;
case '#':printf("ERROR2\n");
break;
default: f='>';
}
break;
case '#':switch(t1)
{
case '#':f='=';
break;
case '(':printf("ERROR3\n");
break;
default: f='>';
}
}
return f;
}

/* 判断c是否为运算符 */
int In(char c)
{
switch(c)
{
case'+':
case'-':
case'*':
case'/':
case'(':
case')':
case'#':return 1;
default:return 0;
}
}

char Operate(char a,char theta,char b)
{
char c;
a=a-48;
b=b-48;
switch(theta)
{
case'+':c=a+b+48;
break;
case'-':c=a-b+48;
break;
case'*':c=a*b+48;
break;
case'/':c=a/b+48;
}
return c;
}

char EvaluateExpression()
{
SqStack *OPTR,*OPND;/* 设OPTR和OPND分别为运算符栈和运算数栈 */
char a,b,c,x,theta;
InitStack(OPTR);
Push(OPTR,'#');
InitStack(OPND);
c=getchar();
GetTop(OPTR,&x);
while(c!='#'||x!='#')
{
if(In(c)) /* 是7种运算符之一 */
switch(Precede(x,c))
{
case'<':Push(OPTR,c); /* 栈顶元素优先权低 */
c=getchar();
break;
case'=':Pop(OPTR,&x); /* 脱括号并接收下一字符 */
c=getchar();
break;
case'>':Pop(OPTR,&theta); /* 退栈并将运算结果入栈 */
Pop(OPND,&b);
Pop(OPND,&a);
Push(OPND,Operate(a,theta,b));
break;
}
else if(c>='0'&&c<='9') /* c是操作数 */
{
Push(OPND,c);
c=getchar();
}
else /* c是非法字符 */
{
printf("ERROR4\n");
}
GetTop(OPTR,&x);
}
GetTop(OPND,&x);
return x;
}

void main()
{
printf("请输入算术表达式（中间值及最终结果要在0～9之间），并以#结束\n");
printf("%c\n",EvaluateExpression());
}

Answer 1

#define MAXSIZE 100
int relation[8][8]={
{1,1,-1,-1,-1,-1,1,1},
{1,1,-1,-1,-1,-1,1,1},
{1,1,1,1,1,-1,1,1},
{1,1,1,1,1,-1,1,1},
{1,1,1,1,1,-1,1,1},
{-1,-1,-1,-1,-1,0,2},
{-1,-1,-1,-1,-1,2,1,1},
{-1,-1,-1,-1,-1,-1,2,0}
};

typedef struct node

{
char data;

struct node *next;

}Snode;

typedef struct

{
char data[MAXSIZE];

int top;
}Stack0;
typedef struct

{
double data[MAXSIZE];

int top;
}Stack1;

typedef struct

{

Snode *front;

Snode *rear;
}LQueue;

void InitStack(Stack0 *s)

{
s->top=0;

}

void InitStack1(Stack1 *s)

{
s->top=0;

}
void push_L(Stack0 *s,char data)

{
s->data[s->top]=data;
s->top++;

}
void push_L1(Stack1 *s,double data)

{
s->data[s->top]=data;
s->top++;
}
void pop_L(Stack0 *s,char *Y)

{
--s->top;
*Y=s->data[s->top];
}

void pop_L1(Stack1 *s,double *Y)

{
--s->top;
*Y=s->data[s->top];
}
char GetTop(Stack0 *s)

{

return s->data[s->top-1];

}

double GetTop1(Stack1 *s)

{

return s->data[s->top-1];

}

void InitQueue(LQueue *Lq)

{

Snode *p;

p=(Snode *)malloc(sizeof(Snode));

p->next=NULL;
Lq->front=Lq->rear=p;
}

void EnQueue(LQueue *Lq,char x)

{

Snode *p;

p=(Snode *)malloc(sizeof(Snode));

p->data=x;

p->next=NULL;

Lq->rear->next=p;

Lq->rear=p;
}

int DelQueue(LQueue *Lq,char *Y)

{

Snode *p;
if(Lq->front==Lq->rear)return 0;

p=Lq->front->next;

*Y=p->data;

Lq->front->next=p->next;

if(Lq->rear==p)Lq->rear=Lq->front;

free(p);

return 1;

}

int opinion_number(char t)

{

if(t<='9'&&t>='0'||t=='.')

return 1;

else
return 0;
}

void dispose_String(char *p)

{
if(*p=='-')*p='N';
for(p=p+1;*p!='\0';p++)

{
if(*p=='-'&&*(p-1)=='(')

*p='N';

}
*p='#';
//*(p+1)='/0';

}

double opreate(double one,char c,double two)

{
double value;
switch(c)
{
case '+':
value=one+two;break;
case '-':
value=one-two;break;
case '*':
value=one*two;break;
case '/':
value=one/two;break;
case 'N':
value=one-two;break;
}
return value;
}
double charTOdouble(char *p)

{
double d;

d=atof(p);

return d;

}
void DelQueue_ALL(LQueue *Lq,char s[])

{
char y;
int i=0;
while(Lq->front!=Lq->rear)

{

DelQueue(Lq,&y);

s[i++]=y;
}
s[i]='\0';
Lq->front=Lq->rear;

}

int panduan(LQueue *Lq)

{
if(Lq->front==Lq->rear)
return 0;
else
return 1;

}
void numerical(char t,LQueue *Lq,char s[],Stack1 *Sta)

{

switch(t)

{

case '+':
if(!panduan(Lq))
break;
else
{
DelQueue_ALL(Lq,s);
push_L1(Sta,charTOdouble(s));
//printf("%f",charTOdouble(s));
break;
}

case '-':

if(!panduan(Lq))
break;
else
{
DelQueue_ALL(Lq,s);
push_L1(Sta,charTOdouble(s));
break;
}

case '*':

if(!panduan(Lq))
break;
else
{
DelQueue_ALL(Lq,s);
push_L1(Sta,charTOdouble(s));
//printf("%f",charTOdouble(s));
break;
}

case '/':

if(!panduan(Lq))
break;
else
{
DelQueue_ALL(Lq,s);
push_L1(Sta,charTOdouble(s));
break;
}
case ')':
if(!panduan(Lq))
break;
else
{
DelQueue_ALL(Lq,s);
push_L1(Sta,charTOdouble(s));
//printf("%f",charTOdouble(s));
break;
}

case '#':
if(!panduan(Lq))
break;
else
{
DelQueue_ALL(Lq,s);
push_L1(Sta,charTOdouble(s));
break;
}

default:
break;

}

}

int suffix(char t)

{

int suf;
switch(t)

{

case '+':
suf=0;
break;
case '-':

suf=1;
break;
case '*':

suf=2;
break;
case '/':
suf=3;
break;
case 'N':
suf=4;
break;
case '(':
suf=5;
break;
case ')':
suf=6;
break;
case '#':
suf=7;
break;
}

return suf;

}

void dispose(Stack0 *s1,Stack1 *s2,char c)

{

int suf1,suf2;
int reust,flag;
double one,two,value;

char s;
suf1=suffix(c);
suf2=suffix(GetTop(s1));
reust=relation[suf2][suf1];

switch(reust)
{

case -1:

push_L(s1,c);

break;

case 0:

pop_L(s1,&s);

break;

case 1:
pop_L(s1,&s);

if(s=='N')
{
pop_L1(s2,&one);
value=opreate(0,s,one);
}
else
{
pop_L1(s2,&two);
printf("two is:%f\n",two);
pop_L1(s2,&one);
printf("one is:%f\n",one);
value=opreate(one,s,two);
//printf("%f",value);
push_L1(s2,value);
dispose(s1,s2,c);
}
break;
}

}

double count_string(char p[])

{
char *q;
char c[100];
Stack0 OPER,*top1;
Stack1 OPND,*top2;
LQueue Lq;
InitQueue(&Lq);
InitStack(&OPER);
InitStack1(&OPND);
push_L(&OPER,'#');
dispose_String(p);

for(q=p;*q!='\0';q++)

{

if(opinion_number(*q))
{
EnQueue(&Lq,*q);

}
else
{

numerical(*q,&Lq,c,&OPND);

//suffix(*q);
dispose(&OPER,&OPND,*q);

//printf("%x,%x\n",top1,top2);
}

}
return GetTop1(&OPND);

}
main()
{

char sr[100]="-2+6+7*(7-36)*5";
double d;
int s;
d=count_string(sr);
printf("%4.5f",d);
scanf("%d",&s);
return 0;
}

这个是我以前写的,能实现+,-,*,/,()和负号的混合运算，数值可以为任意实数

其实最后就是count_string(char *str) 这个函数.

Answer 2

定义一个字符串，让用户输入表达式，
然后浏览表达式，当字符是0~9时就存进一个数组，否则存入另一个字符组。这样就分开了。
但是问题是如果用户输入的不止一位数呢？
解:int
k=0;
while(c[i]>='0'&&c[i]<='9')k=k*10+c[i]-'0';
这样就可以读出多位的整数。
最后：如果用户输入的有小数位呢？
解：if(c[i]=='.')
{
i++;
for(float
m=10;'0'<=c[i]&&c[i]<='9';k*=10,i++)
k+=(c[i]-'0')/m;
}
这样就能读出来小数了.

Answer 3

源程序:(C++)#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define
STACK_INIT_SIZE
100
#define
STACKINCREMENT
10
#define
ERROR
0
#define
OK
1typedef
struct
SqStack1
{
int
*base;
int
*top;
int
stacksize;
}SqStack1;
//建立运算符栈typedef
struct
SqStack2
{
char
*base;
char
*top;
int
stacksize;
}SqStack2;
//建立数字栈void
IntInitStack(SqStack1
*S)
{
S->base=(int
*)malloc(STACK_INIT_SIZE*sizeof(int));
if(!S->base)
exit(ERROR);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}//IntInitStackvoid
CharInitStack(SqStack2
*S)
{
S->base=(char
*)malloc(STACK_INIT_SIZE*sizeof(char));
if(!S->base)
exit(ERROR);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}//CharInitStackint
IntGetTop(SqStack1
*S)
//取栈顶元素
{
int
e;
if((*S).top==(*S).base)
return
0;
e=*((*S).top-1);
return
e;
}//IntGetTopchar
CharGetTop(SqStack2
*S)
//取栈顶元素
{
char
e;
if((*S).top==(*S).base)
return
0;
e=*((*S).top-1);
return
e;
}//IntGetTopint
IntPush(SqStack1
*S,int
e)
{
*(*S).top++=e;
return
OK;
}//IntPushint
CharPush(SqStack2
*S,char
e)
{
*(*S).top++=e;
return
OK;
}//CharPushint
IntPop(SqStack1
*S)
{
int
e;
if((*S).top==(*S).base)
return
0;
e=*--(*S).top;
return
e;
}//IntPopint
CharPop(SqStack2
*S)
{
char
e;
if((*S).top==(*S).base)
return
0;
e=*--(*S).top;
return
e;
}//CharPop
char
Precede(char
a,char
b)
{
int
i,j;
char
Table[8][8]={
'
','+','-','*','/','(',')','#',
'+','>','>','<','<','<','>','>',
'-','>','>','<','<','<','>','>',
'*','>','>','>','>','<','>','>',
'/','>','>','>','>','<','>','>',
'(','<','<','<','<','<','=','
',
')','>','>','>','>','
','>','>',
'#','<','<','<','<','<','
','=',
};
//优先级表格
for(i=0;i<8;i++)
if(Table[0][i]==a)
//纵坐标寻找
break;
for(j=0;j<8;j++)
//横坐标寻找
if(Table[j][0]==b)
break;
return
Table[j][i];
}//Precedeint
Operate(int
a,char
theta,int
b)
//计算表达式值：主要是将大的表达式
{
//转化成小的表达式进行逐步求值
int
c;
if(theta=='+')
c=a+b;
else
if(theta=='-')
c=a-b;
else
if(theta=='*')
c=a*b;
else
c=a/b;
return
c;
}//Operateint
ReadNum(char
s)
//将字符型的数字转化成int型
{
if(s>=49&&s<=57)
//数字的ASCII码所在范围
{
//这儿决定了本程序只能计算一位数的四则运算
s-=48;
return
s;
}
else
return
0;
}//ReadNumint
result(char
*a,SqStack1
*OPND,SqStack2
*OPTR)
//求值
{
char
theta;
int
b,c,i=0;
IntInitStack(OPND);
CharInitStack(OPTR);
CharPush(OPTR,'#');
while(1)
{
if(ReadNum(a[i]))
IntPush(OPND,ReadNum(a[i++]));
else
if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'||a[i]=='#'||a[i]=='('||a[i]==')')
{
switch(Precede(a[i],CharGetTop(OPTR)))
{
case
'<':CharPush(OPTR,a[i++]);break;
case
'=':CharPop(OPTR);i++;break;
case
'>':theta=CharPop(OPTR);
c=IntPop(OPND);
b=IntPop(OPND);
IntPush(OPND,Operate(b,theta,c));
break;
}//switch
}//else
if
if(a[i]=='#'&&CharGetTop(OPTR)=='#')
{
printf("The
result
is
%d.\n",IntGetTop(OPND));
//打印输出表达式值
return
OK;
}
}//while
}//reslutchar
enchange(char
*a)
//此函数将中缀表达式转换为后缀表达式
{
char
ch,b[100];
int
i=0,j=0;
SqStack2
r,*R;
R=&r;
CharInitStack(R);
CharPush(R,'#');
ch=a[i];
while(ch!='#')
{
if(ch=='(')
{
CharPush(R,ch);
ch=a[++i];
}//if
else
if(ch==')')
{
if(CharGetTop(R)!='(')
b[j++]=CharPop(R);
CharPop(R);
ch=a[++i];
}//else
if
else
if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
{
if(Precede(ch,CharGetTop(R))=='<')
CharPush(R,ch);
else
b[j++]=CharGetTop(R);
ch=a[++i];
}//else
if
else
if(ch>=49&&ch<=57)
{
ch-=48;
b[j++]=ch;
ch=a[++i];
}//else
if
}//while
ch=CharPop(R);
while(ch!='#')
{
b[j]=ch;
ch=CharPop(R);j++;
}
b[j]='#';
printf("The
changed
expression
is:
");
for(i=0;b[i]!='#';i++)
//打印输出后缀表达式
{
if(b[i]>=1&&b[i]<=9)
printf("%d",b[i]);
else
printf("%c",b[i]);
}//for
printf(".\n");
return
OK;
}//enchange
void
main()
//主函数，使用自定义函数完成功能
{
char
a[100];
SqStack1
s1,*OPND;
SqStack2
s2,*OPTR;
OPND=&s1;
OPTR=&s2;
printf("Please
enter
an
expression
with
a
end
of
'#'.\n");
printf("The
Expression:");
scanf("%s",&a);
result(a,OPND,OPTR);
enchange(a);
}