一道数据结构题用c或c++

回答1：

/* stack.h 栈的顺序存储表示 */
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */

Status InitStack(SqStack *S)
{ /* 构造一个空栈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;
}

Status GetTop(SqStack S,SElemType *e)
{ /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
if(S.top>S.base)
{
*e=*(S.top-1);
return OK;
}
else
return ERROR;
}

Status Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base==(*S).stacksize) /* 栈满 */
return ERROR;
*((*S).top)++=e;
return OK;
}

Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
}

#include
#include /* atoi() */
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

/* 表达式求值(范围为int类型,输入负数要用(0-正数)表示) */
typedef int SElemType; /* 栈元素类型为整型,改进算法3.4 */
#include"stack.h"

SElemType Precede(SElemType t1,SElemType t2)
{ /* 根据教科书表3.1，判断两符号的优先关系 */
SElemType 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");
exit(ERROR);
}
else
f='<';
break;
//将此函数补充完整
//......
return f;
}

Status In(SElemType c)
{ /* 判断c是否为运算符 */
switch(c)
{
case'+':
case'-':
//将此函数补充完整
//......
}
}

SElemType Operate(SElemType a,SElemType theta,SElemType b)
{
SElemType c;
switch(theta)
{
case'+':c=a+b;
break;
//将此函数补充完整
//......
}
return c;
}

SElemType EvaluateExpression()
{ /* 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈 */
SqStack OPTR,OPND;
SElemType a,b,d,x,theta;
char c; /* 存放由键盘接收的字符串 */
char z[6]; /* 存放整数字符串 */
int i;
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;
//将此函数补充完整
//......
}
else if(c>='0'&&c<='9') /* c是操作数 */
{
//将此函数补充完整
//......
}
else /* c是非法字符 */
{
printf("ERROR3\n");
exit(ERROR);
}
GetTop(OPTR,&x);
}
GetTop(OPND,&x);
return x;
}

void main()
{
printf("请输入算术表达式,负数要用(0-正数)表示,并以=结束\n");
printf("%d\n",EvaluateExpression());
}

回答2：

/*
stack.h
栈的顺序存储表示
*/
#define
STACK_INIT_SIZE
10
/*
存储空间初始分配量
*/
#define
STACKINCREMENT
2
/*
存储空间分配增量
*/
typedef
struct
SqStack
{
SElemType
*base;
/*
在栈构造之前和销毁之后，base的值为NULL
*/
SElemType
*top;
/*
栈顶指针
*/
int
stacksize;
/*
当前已分配的存储空间，以元素为单位
*/
}SqStack;
/*
顺序栈
*/
Status
InitStack(SqStack
*S)
{
/*
构造一个空栈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;
}
Status
GetTop(SqStack
S,SElemType
*e)
{
/*
若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
*/
if(S.top>S.base)
{
*e=*(S.top-1);
return
OK;
}
else
return
ERROR;
}
Status
Push(SqStack
*S,SElemType
e)
{
/*
插入元素e为新的栈顶元素
*/
if((*S).top-(*S).base==(*S).stacksize)
/*
栈满
*/
return
ERROR;
*((*S).top)++=e;
return
OK;
}
Status
Pop(SqStack
*S,SElemType
*e)
{
/*
若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
*/
if((*S).top==(*S).base)
return
ERROR;
*e=*--(*S).top;
return
OK;
}
#include
#include
/*
atoi()
*/
#include
#define
TRUE
1
#define
FALSE
0
#define
OK
1
#define
ERROR
0
typedef
int
Status;
/*
Status是函数的类型,其值是函数结果状态代码，如OK等
*/
typedef
int
Boolean;
/*
Boolean是布尔类型,其值是TRUE或FALSE
*/
/*
表达式求值(范围为int类型,输入负数要用(0-正数)表示)
*/
typedef
int
SElemType;
/*
栈元素类型为整型,改进算法3.4
*/
#include"stack.h"
SElemType
Precede(SElemType
t1,SElemType
t2)
{
/*
根据教科书表3.1，判断两符号的优先关系
*/
SElemType
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");
exit(ERROR);
}
else
f='<';
break;
//将此函数补充完整
//......
return
f;
}
Status
In(SElemType
c)
{
/*
判断c是否为运算符
*/
switch(c)
{
case'+':
case'-':
//将此函数补充完整
//......
}
}
SElemType
Operate(SElemType
a,SElemType
theta,SElemType
b)
{
SElemType
c;
switch(theta)
{
case'+':c=a+b;
break;
//将此函数补充完整
//......
}
return
c;
}
SElemType
EvaluateExpression()
{
/*
算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈
*/
SqStack
OPTR,OPND;
SElemType
a,b,d,x,theta;
char
c;
/*
存放由键盘接收的字符串
*/
char
z[6];
/*
存放整数字符串
*/
int
i;
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;
//将此函数补充完整
//......
}
else
if(c>='0'&&c<='9')
/*
c是操作数
*/
{
//将此函数补充完整
//......
}
else
/*
c是非法字符
*/
{
printf("ERROR3\n");
exit(ERROR);
}
GetTop(OPTR,&x);
}
GetTop(OPND,&x);
return
x;
}
void
main()
{
printf("请输入算术表达式,负数要用(0-正数)表示,并以=结束\n");
printf("%d\n",EvaluateExpression());
}

回答3：

#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;
}

这个是我以前写的,能实现+,-,*,/,()和负号的混合运算

帮同学写的,写的太急了,如果你看懂了,可以自己再去+其他的运算符号到里面

现在被我放在了DLL里面了,导出函数count_string(char *)

要DLL的把邮箱留下

回答4：

表达式求值这样的问题我好像发过一次，不过和你这个不完全符合。

回答5：

这个哥们学过，但是没学会，不好意思了

一道数据结构题 用c或c++

一道数据结构题用c或c++