表达式求值 |
您所在的位置：网站首页 › 表达式求值过程 › 表达式求值 |
|
最近在学习表达式求值问题，想使用C++或C语言实现一个带圆括号的十进制正整数的表达式求值控制台程序。这个问题可以通过栈或者二叉树遍历来解决。记 得以前在学校学习数据结构中栈的应用时看到过，另外编译原理这门课也有讲过。重新翻开一书的P80~P83第3张有关栈相应的章节时，有一个无括号算术表达式的求值问题，其次在对应的光盘上课程设计里头有表达式求值的 相关描述，这里记录如下： [问题描述] 一个算术表达式是由操作数(operand)、运算符(operator)和界限符 (delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：# （7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 [基本要求] （1） 从键盘读入一个合法的算术表达式，输出正确的结果。 （2） 显示输入序列和栈的变化过程。 [选作内容] （1） 扩充运算符集合。 （2） 引入变量操作数。 （3） 操作数类型扩充到实数
相应的C语言代码如下： [cpp] view plaincopy //expression.c #include #include #include #include #include #define TRUE 1 #define FALSE 0 #define Stack_Size 50 char ops[7]={'+','-','*','/','(',')','#'}; /*运算符数组*/ int cmp[7][7]={{2,2,1,1,1,2,2}, /*用来进行比较运算符优先级的矩阵,3代表'=',2代表'>',1代表''、''; break; case 3: pri='='; break; case 0: pri='$'; printf("表达式错误!\n"); break; } return pri; } int Execute(int a, char op, int b) /*运算函数*/ { int result; switch(op) { case '+': result=a+b; break; case '-': result=a-b; break; case '*': result=a*b; break; case '/': result=a/b; break; } return result; } int ExpEvaluation() /*读入一个简单算术表达式并计算其值。optr和operand分别为运算符栈和运算数栈，OPS为运算符集合*/ { int a,b,v,temp; char ch,op; char *str; int i=0; SeqStack optr; /*运算符栈*/ nSeqStack operand; /*运算数栈*/ InitStack(&optr); InitStackn(&operand); Push(&optr,'#'); printf("请输入表达式(以#结束):\n"); /*表达式输入*/ str =(char *)malloc(50*sizeof(char)); gets(str); /*取得一行表达式至字符串中*/ ch=str[i]; i++; while(ch!='#'||GetTop(&optr)!='#') { if(!Isoperator(ch)) { temp=ch-'0'; /*将字符转换为十进制数*/ ch=str[i]; i++; while(!Isoperator(ch)) { temp=temp*10 + ch-'0'; /*将逐个读入运算数的各位转化为十进制数*/ ch=str[i]; i++; } Pushn(&operand,temp); } else { switch(Compare(GetTop(&optr),ch)) { case '': Pop(&optr,&op); Popn(&operand,&b); Popn(&operand,&a); v=Execute(a,op,b); /* 对a和b进行op运算 */ Pushn(&operand,v); break; } } } v=GetTopn(&operand); return v; } void main() /*主函数*/ { int result; result=ExpEvaluation(); printf("\n表达式结果是%d\n",result); }
这其中有几个难点： 1、运算符优先级矩阵的设计，里面的运算符优先级如何比较，里面我觉得涉及到编译原理的知识。 2、使用栈求表达式的值 在开源中国的代码分享中看到了一篇用栈实现表达式求值的一篇文章，作者网名为路伟，网址为：http://www.oschina.net/code/snippet_818195_15722，现在引述如下，算作借鉴吧。 作者用栈ADT实现了，表达式求值问题。 用户输入表达式以字符串形式接收，然后处理计算最后求出值 目前仅支持运算符 '(' , ')' , '+' , '-', '*' , '/' 的表达式求值。 内附源代码和一个可执行程序，无图形界面 代码如下： [cpp] view plaincopy //ElemType.h /*** *ElemType.h - ElemType的定义 * ****/ #ifndef ELEMTYPE_H #define ELEMTYPE_H // 定义包含int和float的共同体 typedef union ET{ float fElem; char cElem; }ET; typedef ET ElemType; //int compare(ElemType x, ElemType y); void visit(ElemType e); #endif /* ELEMTYPE_H */ //mainTest.cpp /** * * 文件名称：mainTest.cpp * 摘 要：利用 ADT-栈 完成表达式求值，表达式求值相关函数定义 **/ #include #include #include #include "DynaSeqStack.h" // 表达式的最大长度 #define MAX_EXPRESSION_LENGTH 100 // 操作数的最大值 #define MAX_OPERAND_LENGTH 50 // 查找字符在串中第一次出现位置 int strpos(const char *str, const char ch) { int i; for(i = 0; i pos) { // ASCII 48~57 为数字 .(小数点) 为 46 if(exp[pos] >= 48 && exp[pos] = 48 && exp[pos + len] base) return false; S->top = S->base; S->stacksize = STACK_INIT_SIZE; return true; } /*------------------------------------------------------------ 操作目的： 销毁栈 初始条件： 栈S已存在 操作结果： 销毁栈S 函数参数： SqStack *S 待销毁的栈 返回值： 无 ------------------------------------------------------------*/ void DestroyStack(SqStack *S) { if(S != NULL) { free(S->base); S = NULL; // 防止野指针 } } /*------------------------------------------------------------ 操作目的： 判断栈是否为空 初始条件： 栈S已存在 操作结果： 若S为空栈，则返回true，否则返回false 函数参数： SqStack S 待判断的栈 返回值： bool 是否为空 ------------------------------------------------------------*/ bool StackEmpty(SqStack S) { return (S.base == S.top); } /*------------------------------------------------------------ 操作目的： 得到栈的长度 初始条件： 栈S已存在 操作结果： 返回S中数据元素的个数 函数参数： SqStack S 栈S 返回值： int 数据元素的个数 ------------------------------------------------------------*/ int StackLength(SqStack S) { return (S.top - S.base); } /*------------------------------------------------------------ 操作目的： 得到栈顶元素 初始条件： 栈S已存在 操作结果： 用e返回栈顶元素 函数参数： SqStack S 栈S ElemType *e 栈顶元素的值 返回值： bool 操作是否成功 ------------------------------------------------------------*/ bool GetTop(SqStack S, ElemType *e) { if(NULL == e) return false; *e = *(S.top - 1); return true; } /*------------------------------------------------------------ 操作目的： 遍历栈 初始条件： 栈S已存在 操作结果： 依次对S的每个元素调用函数fp 函数参数： SqStack S 栈S void (*fp)() 访问每个数据元素的函数指针 返回值： 无 ------------------------------------------------------------*/ void StackTraverse(SqStack S, void (*fp)(ElemType)) { if(NULL == fp) return; for(int i = 0; i top - S->base) == S->stacksize) // 栈满 { // 重新分配内存 S->base = (ElemType *)realloc(S->base, sizeof(ElemType) * (S->stacksize + STACKINCREMENT)); //修改top S->top = S->base + S->stacksize; //修改size S->stacksize += STACKINCREMENT; } *(S->top) = e; S->top++; return true; } /*------------------------------------------------------------ 操作目的： 弹栈——删除栈顶元素 初始条件： 栈S已存在且非空 操作结果： 删除S的栈顶元素，并用e返回其值 函数参数： SqStack *S 栈S ElemType *e 被删除的数据元素值 返回值： bool 操作是否成功 ------------------------------------------------------------*/ bool Pop(SqStack *S, ElemType *e) { if(NULL == S || NULL == e || S->top == S->base) // S为空 或 e为空 或 栈空 return false; S->top--; *e = *(S->top); return true; }
作者使用C语言中的共用体解决了栈的复用，有点类似于C++里面的模版类，这钟做法避免了因为不同的元素类型重复建立栈的数据结构，因为运算数栈和 运算符栈的元素类型是不同的，一个为int、float、double类型，另一个为char型，当然如果使用C++写一个栈的类模版或者直接使用STL 的stack就没这么麻烦了。 最近在学习表达式求值问题，想使用C++或C语言实现一个带圆括号的十进制正整数的表达式求值控制台程序。这个问题可以通过栈或者二叉树遍历来解决。记 得以前在学校学习数据结构中栈的应用时看到过，另外编译原理这门课也有讲过。重新翻开一书的P80~P83第3张有关栈相应的章节时，有一个无括号算术表达式的求值问题，其次在对应的光盘上课程设计里头有表达式求值的 相关描述，这里记录如下： [问题描述] 一个算术表达式是由操作数(operand)、运算符(operator)和界限符 (delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：# （7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 [基本要求] （1） 从键盘读入一个合法的算术表达式，输出正确的结果。 （2） 显示输入序列和栈的变化过程。 [选作内容] （1） 扩充运算符集合。 （2） 引入变量操作数。 （3） 操作数类型扩充到实数
相应的C语言代码如下： [cpp] view plaincopy //expression.c #include #include #include #include #include #define TRUE 1 #define FALSE 0 #define Stack_Size 50 char ops[7]={'+','-','*','/','(',')','#'}; /*运算符数组*/ int cmp[7][7]={{2,2,1,1,1,2,2}, /*用来进行比较运算符优先级的矩阵,3代表'=',2代表'>',1代表''、''; break; case 3: pri='='; break; case 0: pri='$'; printf("表达式错误!\n"); break; } return pri; } int Execute(int a, char op, int b) /*运算函数*/ { int result; switch(op) { case '+': result=a+b; break; case '-': result=a-b; break; case '*': result=a*b; break; case '/': result=a/b; break; } return result; } int ExpEvaluation() /*读入一个简单算术表达式并计算其值。optr和operand分别为运算符栈和运算数栈，OPS为运算符集合*/ { int a,b,v,temp; char ch,op; char *str; int i=0; SeqStack optr; /*运算符栈*/ nSeqStack operand; /*运算数栈*/ InitStack(&optr); InitStackn(&operand); Push(&optr,'#'); printf("请输入表达式(以#结束):\n"); /*表达式输入*/ str =(char *)malloc(50*sizeof(char)); gets(str); /*取得一行表达式至字符串中*/ ch=str[i]; i++; while(ch!='#'||GetTop(&optr)!='#') { if(!Isoperator(ch)) { temp=ch-'0'; /*将字符转换为十进制数*/ ch=str[i]; i++; while(!Isoperator(ch)) { temp=temp*10 + ch-'0'; /*将逐个读入运算数的各位转化为十进制数*/ ch=str[i]; i++; } Pushn(&operand,temp); } else { switch(Compare(GetTop(&optr),ch)) { case '': Pop(&optr,&op); Popn(&operand,&b); Popn(&operand,&a); v=Execute(a,op,b); /* 对a和b进行op运算 */ Pushn(&operand,v); break; } } } v=GetTopn(&operand); return v; } void main() /*主函数*/ { int result; result=ExpEvaluation(); printf("\n表达式结果是%d\n",result); }
这其中有几个难点： 1、运算符优先级矩阵的设计，里面的运算符优先级如何比较，里面我觉得涉及到编译原理的知识。 2、使用栈求表达式的值 在开源中国的代码分享中看到了一篇用栈实现表达式求值的一篇文章，作者网名为路伟，网址为：http://www.oschina.net/code/snippet_818195_15722，现在引述如下，算作借鉴吧。 作者用栈ADT实现了，表达式求值问题。 用户输入表达式以字符串形式接收，然后处理计算最后求出值 目前仅支持运算符 '(' , ')' , '+' , '-', '*' , '/' 的表达式求值。 内附源代码和一个可执行程序，无图形界面 代码如下： [cpp] view plaincopy //ElemType.h /*** *ElemType.h - ElemType的定义 * ****/ #ifndef ELEMTYPE_H #define ELEMTYPE_H // 定义包含int和float的共同体 typedef union ET{ float fElem; char cElem; }ET; typedef ET ElemType; //int compare(ElemType x, ElemType y); void visit(ElemType e); #endif /* ELEMTYPE_H */ //mainTest.cpp /** * * 文件名称：mainTest.cpp * 摘 要：利用 ADT-栈 完成表达式求值，表达式求值相关函数定义 **/ #include #include #include #include "DynaSeqStack.h" // 表达式的最大长度 #define MAX_EXPRESSION_LENGTH 100 // 操作数的最大值 #define MAX_OPERAND_LENGTH 50 // 查找字符在串中第一次出现位置 int strpos(const char *str, const char ch) { int i; for(i = 0; i pos) { // ASCII 48~57 为数字 .(小数点) 为 46 if(exp[pos] >= 48 && exp[pos] = 48 && exp[pos + len] base) return false; S->top = S->base; S->stacksize = STACK_INIT_SIZE; return true; } /*------------------------------------------------------------ 操作目的： 销毁栈 初始条件： 栈S已存在 操作结果： 销毁栈S 函数参数： SqStack *S 待销毁的栈 返回值： 无 ------------------------------------------------------------*/ void DestroyStack(SqStack *S) { if(S != NULL) { free(S->base); S = NULL; // 防止野指针 } } /*------------------------------------------------------------ 操作目的： 判断栈是否为空 初始条件： 栈S已存在 操作结果： 若S为空栈，则返回true，否则返回false 函数参数： SqStack S 待判断的栈 返回值： bool 是否为空 ------------------------------------------------------------*/ bool StackEmpty(SqStack S) { return (S.base == S.top); } /*------------------------------------------------------------ 操作目的： 得到栈的长度 初始条件： 栈S已存在 操作结果： 返回S中数据元素的个数 函数参数： SqStack S 栈S 返回值： int 数据元素的个数 ------------------------------------------------------------*/ int StackLength(SqStack S) { return (S.top - S.base); } /*------------------------------------------------------------ 操作目的： 得到栈顶元素 初始条件： 栈S已存在 操作结果： 用e返回栈顶元素 函数参数： SqStack S 栈S ElemType *e 栈顶元素的值 返回值： bool 操作是否成功 ------------------------------------------------------------*/ bool GetTop(SqStack S, ElemType *e) { if(NULL == e) return false; *e = *(S.top - 1); return true; } /*------------------------------------------------------------ 操作目的： 遍历栈 初始条件： 栈S已存在 操作结果： 依次对S的每个元素调用函数fp 函数参数： SqStack S 栈S void (*fp)() 访问每个数据元素的函数指针 返回值： 无 ------------------------------------------------------------*/ void StackTraverse(SqStack S, void (*fp)(ElemType)) { if(NULL == fp) return; for(int i = 0; i top - S->base) == S->stacksize) // 栈满 { // 重新分配内存 S->base = (ElemType *)realloc(S->base, sizeof(ElemType) * (S->stacksize + STACKINCREMENT)); //修改top S->top = S->base + S->stacksize; //修改size S->stacksize += STACKINCREMENT; } *(S->top) = e; S->top++; return true; } /*------------------------------------------------------------ 操作目的： 弹栈——删除栈顶元素 初始条件： 栈S已存在且非空 操作结果： 删除S的栈顶元素，并用e返回其值 函数参数： SqStack *S 栈S ElemType *e 被删除的数据元素值 返回值： bool 操作是否成功 ------------------------------------------------------------*/ bool Pop(SqStack *S, ElemType *e) { if(NULL == S || NULL == e || S->top == S->base) // S为空 或 e为空 或 栈空 return false; S->top--; *e = *(S->top); return true; }
作者使用C语言中的共用体解决了栈的复用，有点类似于C++里面的模版类，这钟做法避免了因为不同的元素类型重复建立栈的数据结构，因为运算数栈和 运算符栈的元素类型是不同的，一个为int、float、double类型，另一个为char型，当然如果使用C++写一个栈的类模版或者直接使用STL 的stack就没这么麻烦了。 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |