/*文件名: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
《数据结构》（李春葆）-上机指导源程序
5星 · 超过95%的资源 需积分: 30 21 浏览量
2010-04-28
16:51:20
上传
评论
收藏 101KB RAR 举报 
上机指导源程序.rar （91个子文件） 
上机指导源程序 
exp8-4.cpp 5KB excise2.cpp 11KB
exp2-6.exe 17KB exp9-4.cpp 2KB algo3-1.cpp 896B exp2-2.cpp 1KB exp9-5.cpp 2KB exp2-1.cpp 1KB exp1-1.cpp 546B exp9-6.cpp 1KB exp3-2.cpp 1KB excise3.cpp 7KB algo4-2.cpp 5KB algo3-2.cpp 1KB exp2-3.cpp 1KB exp2-6.cpp 4KB algo8-1.cpp 3KB algo8-2.cpp 2KB exp3-5.cpp 2KB exp4-3.cpp 3KB graph.h 1KB exp9-3.cpp 4KB exp11-4.cpp 2KB exp5-3.cpp 1KB algo9-1.cpp 2KB exp3-4.cpp 1KB exp10-7.cpp 9KB exp1-2.cpp 313B exp6-3.cpp 1KB exp11-10.cpp 2KB algo3-3.cpp 820B exp3-3.cpp 1KB algo9-2.cpp 2KB exp7-3.cpp 3KB exp11-9.cpp 2KB exp2-5.cpp 1KB algo2-3.cpp 3KB exp7-7.cpp 1KB exp3-6.cpp 2KB exp12-1.cpp 5KB exp11-7.cpp 2KB exp7-2.cpp 6KB exp5-1.cpp 734B exp5-4.cpp 4KB algo3-4.cpp 1KB exp8-3.cpp 2KB exp11-2.cpp 1KB algo2-2.cpp 2KB exp6-4.cpp 1KB exp1-3.cpp 471B exp8-2.cpp 1KB exp2-7.cpp 3KB exp9-2.cpp 981B exp8-1.cpp 673B exp3-7.cpp 4KB exp7-1.cpp 1KB exp10-1.cpp 896B exp9-7.cpp 2KB exp7-3.exe 17KB exp4-2.cpp 1KB exp7-4.cpp 3KB exp4-4.cpp 1KB excise1.cpp 5KB exp10-4.cpp 4KB exp4-5.cpp 1KB exp4-1.cpp 1KB exp2-4.cpp 1KB algo7-1.cpp 4KB exp9-1.cpp 857B algo2-4.cpp 3KB exp6-2.cpp 1KB exp11-8.cpp 2KB exp7-6.cpp 2KB exp10-3.cpp 2KB exp9-8.cpp 2KB exp11-5.cpp 1KB exp11-3.cpp 1KB exp13-1.cpp 5KB exp3-1.cpp 1KB exp10-6.cpp 7KB exp11-1.cpp 1KB exp10-5.cpp 1KB exp11-6.cpp 2KB exp5-2.cpp 1KB exp9-9.cpp 2KB algo4-1.cpp 3KB algo2-5.cpp 3KB algo2-1.cpp 1KB exp10-2.cpp 1KB exp7-5.cpp 3KB exp10-8.cpp 3KB资源评论
enenenen2015-02-05很不错的资源，非常有用，谢谢分享- dongxiaoyao2013-06-24很不错的资源，非常有用
