//文件名:excise2.cpp
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#define MAXNAME 7 //标识符中的最多字符个数
#define MAXPRIORITY 6 //最大的运算符优先级
#define MAXTOKEN 100 //最大的标识符个数
#define MAXSTACK 100 //栈大小
#define MAXSTRING 101 //表达式中最多的字符个数
#define HASHSIZE 101 //哈希表的大小
#define LASTOPERAND 17 //最后一个运算数的下标
typedef double Value_type;
typedef enum kind_tag {UNARYOP,BINARYOP,OPERAND,LEFTPAREN,RIGHTPAREN,ENDEXPR} Kind_type;
typedef struct
{
char name[MAXNAME]; //标识符名
Kind_type kind; //标识符类型
union
{
int pri; //优先级
Value_type val; //值
} info;
} Token_type;
Token_type lexicon[MAXTOKEN]={ //标识符表
{"#",ENDEXPR}, //0:结束符
{"(",LEFTPAREN}, //1:左括号
{")",RIGHTPAREN}, //2:右括号
{"~",UNARYOP,6}, //3:负号
{"abs",UNARYOP,6}, //4:求绝对值
{"sqrt",UNARYOP,6}, //5:求平方根
{"exp",UNARYOP,6}, //6:求ex
{"ln",UNARYOP,6}, //7:求log2
{"log10",UNARYOP,6}, //8:求log10
{"sin",UNARYOP,6}, //9:求sin
{"cos",UNARYOP,6}, //10:求cos
{"tanh",UNARYOP,6}, //11:求tanh
{"+",BINARYOP,4}, //12:二元"+"
{"-",BINARYOP,4}, //13:二元"-"
{"*",BINARYOP,5}, //14:二元"*"
{"/",BINARYOP,5}, //15:二元"/"
{"%",BINARYOP,5}, //16:二元"%"
{"^",BINARYOP,6}}; //17:二元"^"
int hashtable[MAXTOKEN]; //哈希表
int infix[MAXTOKEN]; //存放中缀表达式
int postfix[MAXTOKEN]; //存放后缀表达式
int inlength; //扫描infix表达式的指针
int postlength; //扫描postfix表达式的指针
int parencount; //表达式中括号个数
int tokencount; //lexicon[]中的标识符个数
int Hash(char *name) //在哈希表中查找name的下标
{
int h=name[0] % HASHSIZE;
while (1)
{
if (hashtable[h]==-1)
break;
else if (strcmp(lexicon[hashtable[h]].name,name)==0)
break; //name在哈希表中
else
{
if (name[1]=='\0')
h+=31;
else
h+=name[1];
h%=HASHSIZE; //找另一个位置
}
}
return abs(h);
}
void MakeHashTable() //构造哈希表
{
int i;
for (i=0;i<HASHSIZE;i++) //置初值
hashtable[i]=-1;
for (i=1;i<=LASTOPERAND;i++)
hashtable[Hash(lexicon[i].name)]=i;
}
Kind_type Kind(int h) //返回lexicon[h]的类型
{
return(lexicon[h].kind);
}
int Priority(int h) //返回lexicon[h]的优先级
{
return(lexicon[h].info.pri);
}
int Leading() //判断是否为开头位置
{
int k;
if (inlength<=-1)
return 1;
else
return (k=Kind(infix[inlength]))==LEFTPAREN || k==UNARYOP || k==BINARYOP;
}
void PutToken(int h) //将lexicon中的下标h添加到infix中
{
inlength++;
infix[inlength]=h;
}
void PutToken1(int h) //将lexicon中的下标h添加到postfix中
{
postlength++;
postfix[postlength]=h;
}
int ExtractWord(char str[],int pos,char *word) //从str[]的pos处提取一个单词
{
int i;
char *pw=word;
for (i=pos;isalpha(str[i]) || isdigit(str[i]);i++) //当前字符为字母或数字时
*pw++=tolower(str[i]); //转化为小写字母后添加到word中
*pw='\0';
return i;
}
int FindWord(char str[],int pos) //找到一个单词,进行相应的处理
{
int h;
char word[MAXTOKEN];
pos=ExtractWord(str,pos,word);
h=hashtable[Hash(word)];
if (h!=-1) //在哈希表中找到时
{
if (Leading()==1)
{
if (Kind(h)==BINARYOP)
{
printf("二元运算符位置不正确\n");
return -1;
}
else
PutToken(h);
}
else
{
if (Kind(h)!=BINARYOP)
{
printf("应为二元运算符\n");
return -1;
}
else
PutToken(h);
}
return pos;
}
else //h==-1时
{
printf(" >>不正确的标识符\n");
return -1;
}
}
int FindNumber(char str[],int pos) //找到一个操作数,进行相应的处理
{
if (Leading()==0)
{
printf("常量位置不正确\n");
return -1;
}
else //将当前识别的操作数添加到lexicon表中
{
lexicon[++tokencount].kind=OPERAND;
lexicon[tokencount].info.val=atof(&str[pos]); //将该操作数串转换成数值
strcpy(lexicon[tokencount].name,"number");
PutToken(tokencount); //将lexicon中对应的下标添加到infix中
for (;isdigit(str[pos]) || str[pos]=='.';pos++); //扫描完该操作数
return pos;
}
}
int FindSymbol(char str[],int pos) //找到一个符号或括号,进行相应的处理
{
int h,k;
char word[MAXTOKEN];
word[0]=str[pos];
word[1]='\0';
pos++;
if ((h=hashtable[Hash(word)])==-1) //在lexicon中找不到该符号
{
printf("表达式中存在不能识别的符号\n");
return -1;
}
else if (Leading()==1) //若之前有"("、一元或二元运算符
{
if (Kind(h)==RIGHTPAREN) //当前符号为")"
{
printf("不应为右括号\n");
return -1;
}
else if (Kind(h)!=BINARYOP) //当前符号不为二元运算符,将其添加到infix中
PutToken(h);
else //当前符号为二元运算符
{
if (strcmp(word,"+")==0); //为"+"时,应是一元"+",不做任何事件
else if (strcmp(word,"-")==0) //为"-"时,应是一元"-",将"~"添加到infix中
PutToken(hashtable[Hash("~")]);
else //其他二元运算符为非法
{
printf(" >>二元运算符不正确\n");
return -1;
}
}
}
else //Leading()=0时
{
if (Kind(h)==BINARYOP || Kind(h)==RIGHTPAREN) //将二元运算符或")"添加到infix中
PutToken(h);
else
{
printf("二元运算符不正确\n");
return -1;
}
}
if ((k=Kind(h))==LEFTPAREN)
parencount++;
else if (k==RIGHTPAREN)
if (--parencount<0) //左、右括号不匹配
{
printf("太多的右括号\n");
return -1;
}
return pos;
}
void GetToken(int &h) //从infix中取一个标识符
{
inlength++;
h=infix[inlength];
}
void GetToken1(int &h) //从postfix中取一个标识符
{
postlength++;
h=postfix[postlength];
}
void Translate() //将中缀表达式infix转换成后缀表达式postfix
{
int St[MAXSTACK];int top=-1; //定义栈及栈指针
int h,h1;
Kind_type type;
postlength=-1;
inlength=-1;
int endright; //取1或0.1:表示一个运算符处理完毕(需考虑优先级)
do
{
GetToken(h);
switch(type=Kind(h))
{
case OPERAND: //为运算符,直接添加到postfix中
PutToken1(h);
break;
case LEFTPAREN: //为"(",将其进栈
top++;
St[top]=h;
break;
case RIGHTPAREN: //为")",出栈运算符添加到postfix中直到遇到"("
h=St[top];top--;
while (top>-1 && Kind(h)!=LEFTPAREN)
{
PutToken1(h);
h=St[top];top--;
}
break;
case UNARYOP: //为一元或二元运算符
case BINARYOP:
endright=0;
do
{
if (top==-1) //栈空
endright=1;
else if (Kind(St[top])==LEFTPAREN)
endright=1;
else if (Priority(St[top])<Priority(h))
endright=1;
else if (Priority(St[top])==Priority(h) && Priority(h)==MAXPRIORITY)
endright=1;
else
{
h1=h; //将当前h放在当前高优先运算符的后面
endright=0;
h=St[top];top--;
PutToken1(h);
h=h1;
}
} while (endright==0);
top++;St[top]=h;
break;
case ENDEXPR:
while (top>-1)
{
h=St[top];top--;
PutToken1(h);
}
break;
}
} while (type!=ENDEXPR);
PutToken1(0); //在postfix中添加ENDEXPR
}
int ProcessExpress(char *instring) //对原表达式进行预处理
{
int len,pos;
inlength=-1;
parencount=0;
tokencount=LASTOPERAND;
len=strlen(instring);
instring[len]='\0';
for (pos=0;pos<len;)
{
if (instring[pos]==' ') //忽略空格字符
pos++;
else if (isalpha(instring[pos])) //处理字母
pos=FindWord(instring,pos);
else if (isdigit(instring[pos]) || instring[pos]=='.') //处理数字
pos=FindNumber(instring,pos);
else //处理符号
pos=FindSymbol(instring,pos);
if (pos==-1)
return 0;
}
if (parencount!=0)
printf("左右括号不匹配\n");
PutToken(0); //在infix中添加ENDEXPR
return 1;
}
void DispInfix() //输出中缀表达式
{
int i;
printf(" 中缀表达式(变换前):");
for (i=0;i<=inlength;i++)
{
if (strcmp(lexicon[infix[i]].name,"number")==0)
printf("%g ",lexicon[infix[i]].info.val);
else
printf("%s ",lexicon[infix[i]].name);
}
printf("\n");
printf(" 中缀表达式(变换后):");
for (i=0;i<=inlength;i++)
printf("%d ",infix[i]);
printf("\n");
}
void DispPostfix() //输出后缀表达式
{
int i;
printf(" 后缀表达式(变换前):");
for (i=0;i<=postlength;i++)
{
if (strcmp(lexicon[post
.rar （83个子文件） 
上机指导源程序 
exp8-4.cpp 2KB excise2.cpp 10KB exp10-9.cpp 2KB exp9-4.cpp 4KB algo3-1.cpp 894B exp2-2.cpp 1KB exp9-5.cpp 1021B exp2-1.cpp 1KB exp1-1.cpp 544B exp9-6.cpp 7KB exp3-2.cpp 1KB excise3.cpp 7KB algo4-2.cpp 5KB algo3-2.cpp 1KB exp2-3.cpp 1KB exp2-6.cpp 3KB algo8-1.cpp 2KB algo8-2.cpp 2KB exp3-5.cpp 2KB exp4-3.cpp 3KB graph.h 1006B exp9-3.cpp 2KB exp5-3.cpp 1KB exp3-4.cpp 1KB exp10-7.cpp 2KB exp1-2.cpp 311B algo3-3.cpp 812B exp8-8.cpp 2KB exp3-3.cpp 1KB exp7-3.cpp 3KB exp10-10.cpp 2KB exp2-5.cpp 1KB algo2-3.cpp 3KB exp7-7.cpp 2KB exp8-6.cpp 1KB exp3-6.cpp 2KB exp12-1.cpp 5KB exp7-2.cpp 4KB exp5-1.cpp 732B exp5-4.cpp 4KB algo3-4.cpp 1KB exp8-3.cpp 4KB algo2-2.cpp 2KB exp1-3.cpp 465B exp8-2.cpp 986B exp2-7.cpp 3KB exp9-2.cpp 1KB exp8-9.cpp 2KB exp8-1.cpp 829B exp3-7.cpp 4KB exp7-1.cpp 1KB exp10-1.cpp 1KB exp9-7.cpp 8KB exp4-2.cpp 1KB exp7-4.cpp 3KB exp8-5.cpp 2KB exp4-4.cpp 1KB excise1.cpp 5KB exp10-4.cpp 2KB exp4-5.cpp 1KB exp4-1.cpp 1KB exp2-4.cpp 1KB algo7-1.cpp 4KB exp9-1.cpp 881B exp5-5.cpp 3KB algo2-4.cpp 3KB exp6-2.cpp 1KB exp7-6.cpp 2KB exp10-3.cpp 1KB exp9-8.cpp 3KB exp8-7.cpp 2KB exp3-1.cpp 1KB exp10-6.cpp 2KB exp11-1.cpp 5KB exp10-5.cpp 1KB exp6-1.cpp 1KB exp5-2.cpp 1017B algo4-1.cpp 3KB algo2-5.cpp 3KB algo2-1.cpp 1KB exp10-2.cpp 1KB exp7-5.cpp 3KB exp10-8.cpp 2KB
评论1