数据结构 一位数表达式求值 调了一天， 手打伤不起啊 哪位路过的搭救一下
表达式求值 调了一天， 手打伤不起啊 哪位路过的搭救一下
//利用栈编写表达式求值程序：输入含有“+”、“-”、“*”、“/”四则运算的表达式，
//其中负数要用（0-正数）表示，
//并以#结束。要求输出表达式的值
#include<malloc.h>
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量
typedef int SElemType; // 定义栈元素类型
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
struct SqStack1
{
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈
struct SqStack2
{
char *base; // 在栈构造之前和销毁之后，base的值为NULL
char *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈
Status InitStack1(SqStack1 &S)
{
// 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE
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 InitStack2(SqStack2 &S)
{
// 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE
S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char)); //动态分配注意前后括号的内容,区分线性和链式两种
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push1(SqStack1 &S,SElemType e)
{
// 在栈S中插入元素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;
S.top++;
return OK;
}
Status Push2(SqStack2 &S,char e)
{
// 在栈S中插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize)
{
S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
if(!S.base)exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top=e;
S.top++;
return OK;
}
Status Pop1(SqStack1 &S,SElemType &e)
{
// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(S.top==S.base)
return ERROR;
e=*(S.top-1);
S.top--;
return OK;
}
Status Pop2(SqStack2 &S,char &e)
{
// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(S.top==S.base)
return ERROR;
e=*(S.top-1);
S.top--;
return OK;
}
Status GetTop1(SqStack1 S)
{
// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
SElemType e;
if(S.top==S.base)
return ERROR;
e=*(S.top-1);
return e;
}
Status GetTop2(SqStack2 S)
{
// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
char e;
if(S.top==S.base)
return ERROR;
e=*(S.top-1);
return e;
}
Status Operate(int a,char theta, int b) //计算函数,此处要注意的是a，b都是字符，是char类型函数中做出相应的转化
{
a=a;
b=b;
if(theta=='+')
return a+b;
else if(theta=='-')
return a-b;
else if(theta=='*')
return a*b;
else if(theta=='/')
return a/b;
else
return ERROR;
}
Status In(char c)
{
if((c>='0')&&(c<'9'))
return ERROR;
else
return OK;
}
char Bijiao(char a,char c) //a为符号帐顶元素，c为新输入的帐的元素，此函数确定运算符之间的优先级
{
if(a=='+')
{
if(c=='+') return '>';
else if(c=='-')return '>';
else if(c=='*')return '<';
else if(c=='/')return '<';
else if(c=='(')return '>';
else if(c==')')return '<';
else if(c=='#')return '>';
}
if(a=='-')
{
if(c=='+') return '>';
else if(c=='-')return '>';
else if(c=='*')return '<';
else if(c=='/')return '<';
else if(c=='(')return '<';
else if(c==')')return '>';
else if(c=='#')return '>';
}
if(a=='*')
{
if(c=='+') return '>';
else if(c=='-')return '>';
else if(c=='*')return '>';
else if(c=='/')return '>';
else if(c=='(')return '<';
else if(c==')')return '>';
else if(c=='#')return '>';
}
if(a=='/')
{
if(c=='+') return '>';
else if(c=='-')return '>';
else if(c=='*')return '>';
else if(c=='/')return '>';
else if(c=='(')return '<';
else if(c==')')return '>';
else if(c=='#')return '>';
}
if(a=='(')
{
if(c=='+') return '<';
else if(c=='-')return '<';
else if(c=='*')return '<';
else if(c=='/')return '<';
else if(c=='(')return '<';
else if(c==')')return '=';
else if(c=='#')return ERROR;
}
if(a==')')
{
if(c=='+') return '>';
else if(c=='-')return '>';
else if(c=='*')return '>';
else if(c=='/')return '>';
else if(c==')')return '>';
else if(c=='#')return '>';
}
if(a=='#')
{
if(c=='+') return '<';
else if(c=='-')return '<';
else if(c=='*')return '<';
else if(c=='/')return '<';
else if(c=='(')return '<';
else if(c=='#')return '=';
}
return 0;
}
Status StackTraverse1(SqStack1 S)
{
// 从栈顶到栈底依次输出栈中的每个元素
SElemType *p = (SElemType *)malloc(sizeof(SElemType));
p = S.top; //这个地方还不用p=S。top-1,因为后续已经有减1的
printf("The Stack is: ");
p--; //已经在此处减1
while(p>=S.base) //等于base还需输出 否则少一个，base还有数据域
{
printf("%d ", *p);
//请填空
p--;
}
printf("\n");
return OK;
}
Status StackTraverse2(SqStack2 S)
{
// 从栈顶到栈底依次输出栈中的每个元素
char *p = (char *)malloc(sizeof(char));
p = S.top; //这个地方还不用p=S。top-1,因为后续已经有减1的
printf("The Stack is: ");
p--; //已经在此处减1
while(p>=S.base) //等于base还需输出 否则少一个，base还有数据域
{
printf("%c ", *p);
//请填空
p--;
}
printf("\n");
return OK;
}
Status Evaluate() //表达式求值的算术优先算法，符帐OPTR，数帐OPND，OP为运算符集合
{
SqStack2 OPTR;
SqStack1 OPND;
char c,x,theta;
int a,b;
InitStack2(OPTR);Push2(OPTR,'#');
InitStack1(OPND);c=getchar();//Push1(OPND,c);
//StackTraverse2(OPTR);
//StackTraverse1(OPND);
while(c!='#'||GetTop2(OPTR)!='#') //Gettop不能直接用整形那个
{
if(!In(c)){Push1(OPND,c-'0');c=getchar();/*StackTraverse1(OPND);printf("%d\n",GetTop1(OPND));*/} //不是运算符的进帐,即数进数帐
else
switch(Bijiao(GetTop2(OPTR),c))
{ //printf("%c\n",GetTop2(OPTR));
case'<':
Push2(OPTR,c);
printf("%c\n",GetTop2(OPTR));
c=getchar();
break;
case'=':
Pop2(OPTR,x);
c=getchar();
break;
case'>':
Pop2(OPTR,theta);
Pop1(OPND,b);
Pop1(OPND,a);
Push1(OPND,Operate(a,theta,b));
// printf("%d\n",GetTop1(OPND));
break;
}
}
StackTraverse2(OPTR);
printf("%d\n",GetTop1(OPND));
return GetTop1(OPND);
}
int main()
{
Evaluate();
return 0;
}
说明：是利用帐来做的，其中有关1的都是数帐，而2的是表示符号帐，注释掉的那些是用来调的~谢谢 有些数据没输出 如3*(9-7)# 9－（9－7）#等 数据结构? c语言
[解决办法]
#include<malloc.h>
#include<stdio.h>
#include<stdlib.h>
#include <string.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100 // 存储空间初始分配量
#define STACKINCREMENT 10 // 存储空间分配增量
typedef int SElemType; // 定义栈元素类型
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
#define NEEDPUSH '<'
#define NEEDCALC '>'
#define SETOFF '='
struct SqStack1
{
SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL
SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈
struct SqStack2
{
char *base; // 在栈构造之前和销毁之后，base的值为NULL
char *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
}; // 顺序栈
Status InitStack1(SqStack1 &S)
{
// 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE
S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); //动态分配注意前后括号的内容,区分线性和链式两种
if(!S.base)exit(OVERFLOW);
memset(S.base, 0,STACK_INIT_SIZE*sizeof(SElemType));
S.top = S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status InitStack2(SqStack2 &S)
{
// 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE
S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char)); //动态分配注意前后括号的内容,区分线性和链式两种
if(!S.base)exit(OVERFLOW);
memset(S.base,0,STACK_INIT_SIZE*sizeof(char));
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push1(SqStack1 &S,SElemType e)
{
// 在栈S中插入元素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;
}
printf("e push 1: %d\r\n",e);
*S.top=e;
S.top++;
return OK;
}
Status Push2(SqStack2 &S,char e)
{
// 在栈S中插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize)
{
S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
if(!S.base)exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
printf("e push 2: %C\r\n",e);
*S.top=e;
S.top++;
return OK;
}
Status Pop1(SqStack1 &S,SElemType &e)
{
// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(S.top==S.base)
return ERROR;
e=*(S.top-1);
*(S.top-1) = 0;
printf("e pop1: %d\r\n",e);
S.top--;
return OK;
}
Status Pop2(SqStack2 &S,char &e)
{
// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(S.top==S.base)
return ERROR;
e=*(S.top-1);
*(S.top-1) = 0;
printf("e pop2: %C\r\n",e);
S.top--;
return OK;
}
Status GetTop1(SqStack1 S)
{
// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
SElemType e;
if(S.top==S.base)
return ERROR;
e=*(S.top-1);
return e;
}
Status GetTop2(SqStack2 S)
{
// 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
char e;
if(S.top==S.base)
return ERROR;
e=*(S.top-1);
return e;
}
Status Operate(int a,char theta, int b) //计算函数,此处要注意的是a，b都是字符，是char类型函数中做出相应的转化
{
a=a;
b=b;
if(theta=='+')
return a+b;
else if(theta=='-')
return a-b;
else if(theta=='*')
return a*b;
else if(theta=='/')
return a/b;
else
return ERROR;
}
Status In(char c)
{
if((c>='0')&&(c<='9'))
return ERROR;
else
return OK;
}
char Bijiao(char a,char c) //a为符号帐顶元素，c为新输入的帐的元素，此函数确定运算符之间的优先级
{
if(a=='+')
{
if(c=='+') return NEEDCALC;
else if(c=='-')return NEEDCALC;
else if(c=='*')return NEEDPUSH;
else if(c=='/')return NEEDPUSH;
else if(c=='(')return NEEDPUSH;
else if(c==')')return NEEDCALC;
else if(c=='#')return NEEDCALC;
}
if(a=='-')
{
if(c=='+') return NEEDCALC;
else if(c=='-')return NEEDCALC;
else if(c=='*')return NEEDPUSH;
else if(c=='/')return NEEDPUSH;
else if(c=='(')return NEEDPUSH;
else if(c==')')return NEEDCALC;
else if(c=='#')return NEEDCALC;
}
if(a=='*')
{
if(c=='+') return NEEDCALC;
else if(c=='-')return NEEDCALC;
else if(c=='*')return NEEDCALC;
else if(c=='/')return NEEDCALC;
else if(c=='(')return NEEDPUSH;
else if(c==')')return NEEDCALC;
else if(c=='#')return NEEDCALC;
}
if(a=='/')
{
if(c=='+') return NEEDCALC;
else if(c=='-')return NEEDCALC;
else if(c=='*')return NEEDCALC;
else if(c=='/')return NEEDCALC;
else if(c=='(')return NEEDPUSH;
else if(c==')')return NEEDCALC;
else if(c=='#')return NEEDCALC;
}
if(a=='(')
{
if(c=='+') return NEEDPUSH;
else if(c=='-')return NEEDPUSH;
else if(c=='*')return NEEDPUSH;
else if(c=='/')return NEEDPUSH;
else if(c=='(')return NEEDPUSH;
else if(c==')')return SETOFF;
else if(c=='#')return ERROR;
}
if(a==')')
{
if(c=='+') return NEEDCALC;
else if(c=='-')return NEEDCALC;
else if(c=='*')return NEEDCALC;
else if(c=='/')return NEEDCALC;
else if(c==')')return NEEDCALC;
else if(c=='#')return NEEDCALC;
}
if(a=='#')
{
if(c=='+') return NEEDPUSH;
else if(c=='-')return NEEDPUSH;
else if(c=='*')return NEEDPUSH;
else if(c=='/')return NEEDPUSH;
else if(c=='(')return NEEDPUSH;
else if(c=='#')return SETOFF;
}
return 0;
}
Status StackTraverse1(SqStack1 S)
{
// 从栈顶到栈底依次输出栈中的每个元素
SElemType *p = (SElemType *)malloc(sizeof(SElemType));
p = S.top; //这个地方还不用p=S。top-1,因为后续已经有减1的
printf("The Stack is: ");
p--; //已经在此处减1
while(p>=S.base) //等于base还需输出 否则少一个，base还有数据域
{
printf("%d ", *p);
//请填空
p--;
}
printf("\n");
return OK;
}
Status StackTraverse2(SqStack2 S)
{
// 从栈顶到栈底依次输出栈中的每个元素
char *p = (char *)malloc(sizeof(char));
p = S.top; //这个地方还不用p=S。top-1,因为后续已经有减1的
printf("The Stack is: ");
p--; //已经在此处减1
while(p>=S.base) //等于base还需输出 否则少一个，base还有数据域
{
printf("%c ", *p);
//请填空
p--;
}
printf("\n");
return OK;
}
Status Evaluate() //表达式求值的算术优先算法，符帐OPTR，数帐OPND，OP为运算符集合
{
SqStack2 OPTR;
SqStack1 OPND;
char c,x,theta;
int a,b;
InitStack2(OPTR);
Push2(OPTR,'#');
InitStack1(OPND);
c=getchar();//Push1(OPND,c);
//StackTraverse2(OPTR);
//StackTraverse1(OPND);
while(c!='#'
[解决办法]
GetTop2(OPTR)!='#') //Gettop不能直接用整形那个
{
if(!In(c))
{
Push1(OPND,c-'0');
c=getchar();/*StackTraverse1(OPND);printf("%d\n",GetTop1(OPND));*/
} //不是运算符的进帐,即数进数帐
else
{
switch(Bijiao(GetTop2(OPTR),c))
{ //printf("%c\n",GetTop2(OPTR));
case NEEDPUSH:
Push2(OPTR,c);
c=getchar();
break;
case SETOFF:
Pop2(OPTR,x);
printf("case SETOFF %C\n",theta);
c=getchar();
break;
case NEEDCALC:
Pop2(OPTR,theta);
Pop1(OPND,b);
Pop1(OPND,a);
Push1(OPND,Operate(a,theta,b));
// printf("%d\n",GetTop1(OPND));
break;
}
}
}
// StackTraverse2(OPTR);
printf("%d\n",GetTop1(OPND));
return GetTop1(OPND);
}
int main()
{
Evaluate();
return 0;
}
代码改好了，最关键的错误是少了个=号 <= "9"
Status In(char c)
{
if((c>='0')&&(c<='9'))
return ERROR;
else
return OK;
}
