上篇写了MFC界面搭建,这篇写实现计算。涉及到数据结构,对新手很不友好。
一些园友在参考本文进行实现时遇到一些问题,程序有些老了,没有进行修正,源码在gitee可下<https://gitee.com/foxerz2077/mfc/tree/master/>。程序程序最后处理CString和char[]有些问题,VS2017可以正常处理,有些版本的IDE不支持这里的处理方法,需要了解CString和 char *之间的转换,作为一个参考方法,博客内有再提到这个。
这虽然是MFC程序,但是能灵活地分离后台代码,自行构建控制台程序,本文的程序一开始只是个“黑框框”程序,后来把代码包装进了MFC。代码里有些预处理宏定义等没有加上,需要根据需求改动一下。
上篇文章链接:C++做四则运算的MFC计算器(一)MFC界面创建
概要:
- 中缀表达式与后缀表达式
- 栈的相关实现
- 用栈将中缀表达式转换成后缀表达式
- 用栈计算后缀表达式
- 等号按钮功能,显示计算结果
中缀表达式与后缀表达式
中缀:(60-20)/(5-1)。小学就学的东西
后缀:60 20 – 5 1 - /,为增加可读性,以“#”做分隔符,60#20#-#5#1#-#/。
后缀计算:从左到右遇到符号就计算符号左边的两个数并写上新值,即优先的运算符相对在左。上例中遇到第一个‘-’算60-20得40,遇到第二个“-”计算5-1得4,遇到“/”计算30/3的10,结果是10。
对比:中缀式人看起来方便,后缀式没有括号,计算顺序从前到后,用计算机操作起来的逻辑简单。
栈的相关实现
输入的值都是字符,所以需要一个字符结构的栈;在计算数时还需要一个处理数字结构的栈。
字符和数值的栈结构体分别命名SqStack和SqStackN。
然后实现栈初始化、进栈、出栈等栈的操作函数。
在工程中,同时把栈结构体和操作函数声明在新建的头文件xxx.h中,或者工程中其他头文件如stdafx.h,新建一个cpp文件实现函数体。
这里的栈和操作函数是自己动手定义的,可以直接用STL中的栈,使用比较方便。
栈内数据用的是 char ,在最后处理CString时可能会因IDE不支持导致出错,需要了解CString与char *之间的转换,我找了一篇比较详细的博客CString用法总结。
1 struct SqStack { 2 char data[maxsize]; 3 int top; 4 }; 5 struct SqStackN { 6 double data[maxsizen]; 7 int top; 8 }; 9 //栈操作函数—字符 10 void initStack(SqStack *&s); 11 bool Push(SqStack *&s, char e); 12 bool Pop(SqStack *&s, char &e); 13 bool GetTop(SqStack *s, char &e); 14 void DestroyStack(SqStack *&s); 15 bool StackEmpty(SqStack *s); 16 //栈操作函数—数字 17 void initStack(SqStackN *&s); 18 bool Push(SqStackN *&s, double e); 19 bool Pop(SqStackN *&s, double &e); 20 bool GetTop(SqStackN *s, double &e); 21 void DestroyStack(SqStackN *&s); 22 bool StackEmpty(SqStackN *s); 23 24 //后缀表达式转换函数 25 void trans(char* exp, char postexp[]); 26 //计算后缀表达式函数 27 double calculate(char* postexp);
头文件主要声明
1 void initStack(SqStack *&s) { 2 s = new SqStack(); 3 s->top = -1; 4 } 5 bool Push(SqStack *&s, char e) { 6 if (s->top == maxsize-1) 7 return false; 8 s->top++; 9 s->data[s->top] = e; 10 return true; 11 } 12 bool Pop(SqStack *&s, char &e) { 13 if (s->top == -1) 14 return false; 15 e = s->data[s->top]; 16 s->top--; 17 return true; 18 } 19 bool GetTop(SqStack *s, char &e) { 20 if (s->top == -1) 21 return false; 22 e = s->data[s->top]; 23 return true; 24 } 25 void DestroyStack(SqStack *&s) { 26 free(s); 27 } 28 bool StackEmpty(SqStack *s) { 29 return (s->top == -1); 30 } 31 32 void initStack(SqStackN *& s){ 33 s = new SqStackN(); 34 s->top = -1; 35 } 36 37 bool Push(SqStackN *& s, double e) 38 { 39 if (s->top == maxsizen - 1) 40 return false; 41 s->top++; 42 s->data[s->top] = e; 43 return true; 44 } 45 46 bool Pop(SqStackN *& s, double & e) 47 { 48 if (s->top == -1) 49 return false; 50 e = s->data[s->top]; 51 s->top--; 52 return true; 53 } 54 55 bool GetTop(SqStackN * s, double & e) 56 { 57 if (s->top == -1) 58 return false; 59 e = s->data[s->top]; 60 return true; 61 } 62 63 void DestroyStack(SqStackN *& s){ 64 free(s); 65 } 66 67 bool StackEmpty(SqStackN * s) 68 { 69 return (s->top == -1); 70 }
cpp函数定义
用栈将中缀表达式转换成后缀表达式
从左向右扫描中缀,遇到数字就添加到后缀中,遇到运算符进行栈处理,而栈的处理依赖于运算符优先级,优先级高的靠近栈顶,保证在后缀式中先运算的运算符靠前。结束后后缀式仍是字符数组。
写个函数tans(),有2个参数char * exp和char postexp[ ],
先初始化一个字符栈指针s,char e用来操作栈顶元素,int p作为postexp数组的下标。用循环扫描exp
while (*exp != ' ') {switch(*exp){case:case:case:default}......}
扫描到数字字符时直接加到后缀式中,并加上 ‘ # ’ 以分割。
其他情况无非是+、-、*、/、(、)这6个符号。
(、)优先级最高,在括号之间的运算符一定比括号之外的优先运算,遇到 ‘ ( ’ 即进栈,遇 ‘ ) ’ 即出栈栈顶元素直到出来的是 ‘ ( ’ 。因此栈中不会有 ‘ ) ’ 。
*、/优先级其次,先判断栈顶是什么,栈顶是*、/则将其出栈到后缀式,栈顶是+、-则将 ‘ * ’ 或 ‘ / ’ 进栈,保证后缀中乘和除的优先运算。
+、-优先级最低,这是栈顶元素不管是+-*/都出栈至后缀式,但栈顶是 ‘ ( ’ 时就不需要出栈,‘ ( ’可以看作是一个新的运算起点,将+或-进栈即可。
exp扫描后栈可能还会有运算符,将剩下的都出栈至后缀式。再为后缀式加结束标识 ‘ ’ ,销毁栈释放空间。
1 void trans(char* exp,char postexp[]) {
2 char e;
3 SqStack *s; initStack(s); // 即SqStack s = new SqStacck()
4 int p = 0;//postexp的下表
5 while (*exp != '