【数据结构】book3_3 表达式求值

#include<iostream>
#include <stdlib.h>
using namespace std; typedef int Status;
const int TRUE=;
const int FALSE=;
const int OK=;
const int ERROR=;
const int INFEASIBLE=-;
const int overflow=-;
const int STACK_INIT_SIZE=;
const int STACKINCREMENT=; typedef struct{
char *base;
char *top;
int stacksize;
}SqStack; //构造一个空栈
Status InitStack(SqStack &S)
{
S.base=(char*)malloc(sizeof(char)*STACK_INIT_SIZE);
if(!S.base) exit(overflow);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
} Status GetTop(SqStack S,char &e)
{
if(S.top==S.base) return ERROR;
e=*(S.top-);
return OK;
} Status Push(SqStack &S,char 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;
return OK;
} Status Pop(SqStack &S,char &e)
{
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
} Status StackEmpty(SqStack S){
if(S.base==S.top)
return TRUE;
else
return FALSE;
} Status ClearStack(SqStack &S)
{
S.top = S.base ;
return TRUE;
} Status DestroyStack(SqStack &S)
{
if(S.base!=NULL)
{
free(S.base);
S.stacksize=;
S.top=NULL;
}
return TRUE;
}
#include"book3_3.h"

#define ND 0  //操作数标志
#define TR 1 //操作符标志 //存放运算符的优先顺序的矩阵 op1是竖排的 op2是横排的 e表示错误
const static char Order[][]=
{{'>','>','<','<','<','>','>'}, // +
{'>','>','<','<','<','>','>'}, // -
{'>','>','>','>','<','>','>'}, // *
{'>','>','>','>','<','>','>'}, // /
{'<','<','<','<','<','=','e'}, // (
{'>','>','>','>','e','>','>'}, // )
{'<','<','<','<','<','e','='}}; // #
// + - * / ( ) # //比较两个操作符的优先级 op1和op2的顺序不能错
Status compOperator(char op1, char op2, char &result)
{
int t1=,t2=;
//找到两个操作符的优先级在矩阵中的位置
switch(op1)
{
case '+': t1=; break;
case '-': t1=; break;
case '*': t1=; break;
case '/': t1=; break;
case '(': t1=; break;
case ')': t1=; break;
case '#': t1=; break;
default: return ERROR; break;
}
switch(op2)
{
case '+': t2=; break;
case '-': t2=; break;
case '*': t2=; break;
case '/': t2=; break;
case '(': t2=; break;
case ')': t2=; break;
case '#': t2=; break;
default: return ERROR; break;
} result=Order[t1][t2]; if(result=='e')
return ERROR;
else
return OK;
} int decideNDorTR(char t) //判断输入的字符是操作符还是操作数
{
if(t>=&&t<=) //数字的ascii码范围
{
return ND;
}
else if(t=='+' || t=='-' || t=='*' || t=='/' || t=='(' || t==')' || t=='#')
{
return TR;
}
else
{
printf("error");
return ERROR;
} } char myCalculate(char op,char num1,char num2) //字符型的运算符的计算
{
char num;
switch(op)
{
case '+': num= num1+ num2; break;
case '-': num= num1- num2; break;
case '*': num= num1* num2; break;
case '/': num= num1/ num2; break;
default: printf("error");break;
}
return num;
} //计算表达式的函数 注意运算结果大小不能超过255 char型
char EvaluateExpression(char *p, int length)
{
SqStack OPTR, OPND;
InitStack(OPTR);
InitStack(OPND);
Push(OPTR,'#'); while(*p != '\0')
{
char t = *(p++);
int ND_TR=decideNDorTR(t); //判断是操作符 还是 操作数 if(ND_TR == ND) //操作数
{
//操作数有可能是多位的
char num=;
while(t>=&&t<=) //字符 0-9
{
num = num * + t - ;
t=*(p++);
}
p--; //对于 12+3 这样的情况 在取完数后 p=3 +被取走了 需要退一个 把操作符还回去
Push(OPND,num);
}
else if(ND_TR == TR) //操作符
{
char order;
char op1;
char op2= t;
GetTop(OPTR,op1);
compOperator(op1, op2, order);
switch(order)
{
case '>': //若栈中的操作符优先级高 则取出操作数的前两个做运算 把运算后的操作符弹出 运算结果压入
{
char num1,num2,num;
char tmp;
Pop(OPND,num2);
Pop(OPND,num1);
num = myCalculate(op1,num1,num2);
Push(OPND,num);
Pop(OPTR,tmp);
p--; //这里p要退回 让op2再进行新一轮判断
break;
}
case '<': //若栈中操作符优先级低 新操作符进栈
{
Push(OPTR,op2);
break;
}
case '=': //()或# 弹出 脱括号
{
char tmp;
Pop(OPTR,tmp); break;
}
default:
{
break;
}
}
} }
char e;
GetTop(OPND,e);
return e; } void main()
{
char p[]="(11+2)*3-28+123-52#";
char ans;
ans = EvaluateExpression(p, );
printf("%d",ans);
getchar(); }

写了好半天啊 关系总是理不清楚的感觉

上一篇:Java生成静态HTML文件


下一篇:x