大家帮我瞧瞧呗,看看我这个这个多位数表达式运算(栈)
我这个多位数表达式运算(栈)编译没问题,就是运行的结果被不对,新手还是没有想出来。[local]2[/local]求教
表达式运算优先级用数组存储表达方式.zip
(2.63 KB)
[local]2[/local]求教
#include<stdio.h> #include<stdlib.h> #include<string.h> #define OVERFLOW -2 #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 char expr[255] = ""; /* 存放表达式串 */ char *ptr =expr; //全局变量 typedef char SElemType; typedef struct { SElemType *base; //栈底指针,栈构造之前和销毁之后,base的值NULL, SElemType *top; // 栈顶指针 int stacksize; //当前已分配的存储空间,以栈里的元素占字节大小为单位 }SqStack; int InitStack(SqStack &S) //构造一个空栈 { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); //申请一片STACK_INIT_SIZE*sizeof(SElemType)大小内存空间。以S.base为基址 if(!S.base) //S.base为空则分配失败 { return ERROR; } S.top=S.base; //空栈:栈顶等于栈底 S.stacksize=STACK_INIT_SIZE; //容量等于初始分配容量 return OK; } int GetTop(SqStack S,SElemType &e) { //若栈不空,则用e返回S的栈顶元素,并返回OK,否则返回ERROR; if(S.base==S.top) { return ERROR; } else e=*(S.top-1); //--S.top return OK; } int Push(SqStack &S,SElemType e) //插入元素e为新的栈顶元素 { //先判断栈是否满了,栈满则增加空间 if(S.top-S.base>STACK_INIT_SIZE) //栈满,追加存储STACKINCREMENT内存空间 { 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; } int Pop(SqStack &S,SElemType &e) //若栈不空,若删除S的栈顶元素,用e返回其值,并返回OK,否则返回false { if(S.top==S.base) { return ERROR; } e=*--S.top; return OK; } int In(SElemType c) //判断c是否为运算符 { switch(c) //return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#') { //为另一种判断条件,有相等的返回1,不想等返回1. case '+': case '-': case '*': case '/': case '(': case ')': case '#':return OK; default: return ERROR; } } /*判断运算符优先权,返回优先权高*/ SElemType Precede(SElemType t1,SElemType t2) { int i=0,j=0; //将书中的运算符优先级放在一个数组中 static char array[49]={ '>', '>', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '<', '<', '<', '<', '<', '=', '!', '>', '>', '>', '>', '!', '>', '>', '<', '<', '<', '<', '<', '!', '='}; switch(t1) {/* i为下面array的横标*/ 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; } switch(t2) { /* j为下面array的纵标 */ 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; } return (array[7*i+j]); /* 返回运算符 */ } int Operate(int a,SElemType theta,int b) //因为SElemType是char类型,所以输入的整数都是字符,在内存的要把其ascii值变成相应的整数值 { switch(theta) { case '+' : return (a+b); case '-' : return (a-b); case '*' : return (a*b); case '/' : return (a/b); } return 0; } int num(int n) { int a; char p[10]; itoa(n,p,10); //将数字转换为相应进制的字符串,形参分别对应欲转换的数据,目标串的地址,转换后的进制 a=strlen(p); return a; } SElemType EvaluateExpression()//运算操作函数 { SElemType a,b,x,c,theta,e; int n,m; SqStack OPND; SqStack OPTR; InitStack(OPTR); Push(OPTR,'#'); InitStack(OPND); c=*ptr++; GetTop(OPTR,e); while(c!='#'||e!='#') { if(!In(c)) { ptr=ptr-1; m=atoi(ptr); //atoi把字符型变为整型,所以是取前面的数字段 n=num(m); Push(OPND,m); ptr=ptr+a; c=*ptr++; } else { switch(Precede(e,c)) { case '<': Push(OPTR,c); c=*ptr++; break; case '=': Pop(OPTR,x); c=*ptr++; break; case '>': Pop(OPTR,theta); // 退栈并将运算结果入栈 Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b)); break; } GetTop(OPTR,e); } GetTop(OPND,e); return e; } } int main() { printf("请输入算术表达式(输入值和中间结果及最终值最终结果要在0~9之间)," "并以#结束\n"); printf("例如:3*(7-5)#\n"); do{ gets(expr); }while(!*expr); printf("%d",EvaluateExpression()); system("pause"); return 0; }