简单的lisp算术表达式计算器

沈阳航空工业学院课 程 设 计（说明书）简单 LISP 算术表达式计算器班级 / 学号 7402101-024 学 生 姓 名 田青林 指 导 教 师 贾亮 简单算术表达式计算器- 1 -一、 题目分析 本题目是设计一个简单的 LISP 算术表达式计算器。 简单 LISP 算术表达式（以下简称表达式）定义如下: (1) 一个 09 的整数；或者 (2) （运算符 表达式 表达式） 例如，6， （+45 ） ， （+（+25 ）8）都是表达式，其值分别为 6，9 和 15。算术表达式不同于普通的普通的表达式，不是简单的从左向右（或是从右向左）的计算， 它包含了算术运算符和算术量，计算的过程就是要根据算术运算符的优先关系将其所对应得量的每一位进行计算，最后得到结果。初步思想是建立一个栈列，将变量存储进去，通过每步中对头两个算术量的求和，最后将结果存储到栈头，输出。运算的要点如下：从左到右地扫描表达式（1）扫描到操作数时,直接输出。（2）第二次扫描到（时进行递归调用，从头进行扫描。（3）扫描到算术量时将其压入栈，并与前一个压入栈的算术量求和。（4）最后的栈头元素即为所求。二、 设计过程（程序流程图） 根据本课设题目的要求，本设计程序依据利用栈依次从里向外计算括号内数的思想设计成一个简单的 LISP 算术表达式计算器。该程序首先建立一个栈，通过PUSH 函数和 POP 函数的入栈，出栈功能实现栈中元素“先进后出，后进先出”的特性。然后动态建立一大小为 K 的整型数组，把开辟的数组指针赋给 a,从而实现栈函数的构造过程。然后再建立栈的对象，再建立一个字符型数组 ch，然后向该数组输入表达式，最后进入表达式判断阶段。若 LISP 表达式为一操作数，则直接输出；若该表达式为运算符，则经过主函数的扫描计算，最终输出结果。2.1 栈的建立这是一个子函数 stack(int k=100)，首先建立一个足够大的栈，动态定义其大小为 100，然后对其置空初始化，再根据判断其是否为空返回不同的值。其设计流程图如图 1。简单算术表达式计算器- 2 -图 1：栈的建立 2.2 入栈这是一个子函数 PUSH，首先赋给输入值 k，再判断栈是否为非空，若为非空则将 k 压入栈中；若为满栈，则输出错误。其流程图如图 2 所示。图 2：PUSH 函数2.3 出栈定义栈 a初始化栈 a 是否为空？Top=-1 Top=big返回 top开始YN开始输入 k 值!full( )？atop=ktop+ wrong push返回NY简单算术表达式计算器- 3 -这是一个子函数 POP，首先判断是否非空，若是则输出栈头元素 atop，若不是，则返回 0 并参与运算。其设计流程图如图 3 所示。图 3：POP 函数2.4 构建函数首先动态开辟一个大小为 K 的数组，然后把开辟数组的指针赋给 a,然后将 K-1赋给 Big,将-1 赋给 Top，从而实现函数的构造过程，函数构造完毕，退出此进程，此段程序结束。其设计流程图如图 4 所示。图 4：构建函数2.5 主函数这是整个程序的核心所在。首先要建立一个栈 V1，将所求表达式赋值给字符变开始!empty( )？返回 atoptop-返回 0结束开始动态开辟一个大小为 k 的数组把开辟数组的指针赋给 abig=k-1top=-1结束简单算术表达式计算器- 4 -量 ch。接下来就是从头扫描字符，这也是一个循环的过程。若 chi不是（ ，则直接入栈，若是则跳向下下个字符， ；再判断是不是（，若不是，则将 chi入栈，跳向下一个字符；再判断是不是（，若还不是则入栈。这其中若是，若是则都要进行从头扫描。接下来进行一个总的判断“！=（i+输出 v1.pop()chi!=)？将 chi入栈NYNYNY NNYNYY结束简单算术表达式计算器- 6 -图 5:主函数图 6：计算器界面（2）每一次输入数据以后，都要回车再输入 ctrl+z，然后再回车，就能得到所需结果。这其中 ctrl+z 是结束流。首先计算 6。如图 7 所示。简单算术表达式计算器- 7 -图 7：计算“6”（3）计算（+45） ，如图 8 所示。图 8：计算（+45）（4）计算（+（+（+12） （+34） ） （+（+56） （+78） ） ） ，计算过程如图 10 所示。简单算术表达式计算器- 8 -图 10：计算（+（+（+12） （+34） ） （+（+56） （+78） ） ）四、结论 本程序十分简洁，且理解上也比较容易，完成了简单的算术表达式的计算问题，但是没能够实现其四则运算的问题，还有按照原思路应该是建立两个栈，一个存放数值，一个存放运算符，比较运算符的优先级然后对其控制的值作相应的运算。由于本人软件知识有限，所以得出的程序只是实现了片面的功能，对运算符采取了跳过的处理方式，只对表达式中的值作和，再输出。经过了将近两周的软件课设，根据题目要求对源程序作了相当大的改动，这其中包括对缀余程序的删除，对错误程序的修正。另外程序参考了网上的模版，但其中不明白的地方有很多，问了很多人，也查阅了以前学过的关于栈的知识，最后也不是彻底的能弄明白。我对于我的程序不是很满意，因为这并不是一个简单的 LISP计算器，计算器最起码能进行四则运算，但此计算器只能完成类似题目中所给的运算。虽然程序有些欠缺的地方，但毕竟是花了十多天的时间在程序上，收获还是很多的，算是对一学期的软件课作了一个总结，也从搜索资料中学会了运用图书馆和网络，总之软件课设使我受益匪浅，对以后的工作和学习都有很大的帮助。五、程序清单简单算术表达式计算器- 9 -#includeint y=0;class stackpublic:stack(int k=100)a=new intk;big=k-1;top=-1;bool empty()return top=-1;bool full()return top=big; /入栈void push(int k)if(!full()a+top=k;elsecoutch);int i=0;while(chi!=0)if(chi=()i=i+2;if(chi=()continue;v1.push(chi-48);i+;if(chi=()continue;v1.push(chi-48);else if(chi!=)v1.push(chi-48);if(chi!=)if(chi=)v1.push(v1.pop()+v1.pop();i+;cout“结果： “endl;