在深入浅出数据结构(7)的末尾,我们提到了栈可以用于实现计算器,并且我们给出了存储表达式的数据结构(结构体及该结构体组成的数组),如下:
- //SIZE用于多个场合,如栈的大小、表达式数组的大小
- #define SIZE 1000
- //表达式的单个元素所使用的结构体
- typedef struct elem {
- int num = 0; //若元素存储操作数则num为该操作数
- char oper = '='; //若元素存储操作符则oper为该操作符
- bool IsNum = false; //用于判断元素是否为操作数
- }
- Elem;
- Elem Expression[SIZE];
可能有读者会疑惑我们为什么将 num 定义为 int,我们这么做的原因是为了简便,或者说就是偷懒吧,因为如果要支持使用者输入小数,那么我们的程序在获取、处理输入方面的代码会更加复杂一点╮(╯_╰)╭。关于如何获取、处理输入,我们将在本文的最后给出答案(同时也会给出完整的计算器程序代码,或者说是给出完整的只支持整数输入的、不具备差错纠错能力的四则运算计算器 %>_<%)
目前,我们先将获取、处理输入的问题放在一边,先关注于计算器实现的 "核心部分",或者说需要运用栈的部分。
对于只有两个操作数的表达式,如 a+b、a-b、a*b、a/b,计算起来是很简单的。因为已经确定了是两个操作数,所以处理表达式的步骤就是:取第一个操作数,确定操作符,取第二个操作数,计算(即依次计算);或者说是:取操作符,取左、右操作数,计算。这样的简单的表达式不需要什么特别的技巧,自然也用不上 "先进后出" 的栈。
对于有多个操作数,但操作符优先级一样的表达式,如 a+b+c+d、a-b-c+d 之类的,计算起来也很简单,步骤类似于上一段,依然是依次计算,这样的表达式依然不需要什么特别的技巧(也就是不需要用栈)。
但是,对于四则运算混合的表达式,如 a+b*c-d 之类的,计算就不能再像之前那样了(即依次计算),因为我们要考虑到优先级的问题。显然的,如果我们取到 a、'+'、b 后就直接计算 a+b 的值然后进行下一步运算是错的,这违背了运算符的优先级顺序。更甚者,如 a+b*(c-d) 这样带括号的,我们的优先级处理还会更麻烦。那么我们该怎么应对这样的表达式呢?显然,我们一直在谈的栈要准备出场了!
但是在介绍栈如何解决计算表达式问题之前,我们还要先介绍一些预备知识。
对于混合的四则运算表达式,处理的难点显然就是操作符的优先级问题,当然,还有不属于运算符的操作符,'('和')'的处理问题。回顾前两种表达式(即没有优先级问题的那两种特殊的表达式),我们发现,对于 "依次计算"(没有优先级问题)的表达式,我们处理起来是非常方便的,因此,我们是不是可以找一找,看有没有办法将存在优先级问题的表达式转换为 "依次计算" 的表达式呢?
显然是有的,我们很轻松地就能看出 a+b*c-d 可以变为 b*c+a-d,而带括号的也可以去掉括号,如 a+b*(c-d)=c-d*b+a(从数学角度来说这个表达式不等于原先带括号的,但是我们的视角为计算机,或者说要求为 "依次计算",不考虑优先级)。但是要让计算机做到我们刚才做的这种转换,嗯,不是不可以,但是很难。不过别灰心,我们可以将表达式转换为另一种符合 "依次计算" 的特殊表达式(日常生活中见不到的表达式),而且转换过程很轻松,并且转换后得到的表达式对于编程实现来说比之前的两种更轻松!
让我们先把如何转换暂且压下(不要急,迟早都是会说的),先来看看这转换后的特殊表达式特殊在哪,有什么名儿没。
首先我们要明白,表达式总是由操作数和操作符组成的,且一个操作符总是对应了两个操作数,比如 a+b = 中'+'对应 a 和 b。而像 a+b*c = 这样的多操作符表达式中,'*'对应 b 和 c,'+'则对应 a 和 b*c 的结果,依然是一个操作符对应两个操作数,因为一个操作符和两个操作数即一个结果、一个新的数。
既然一个操作符对应两个操作数,那么就带来一个选择问题:操作符写在哪?这个问题可能世界上 99% 的人都没考虑过,因为我们都已经习惯了 "将操作符写在两个操作数的中间",比如 "a 加上 b" 的表达式的 "写法" 就是 a+b,将'+'写在 a 和 b 的中间。"a 加上 b 再加上 c" 则写作 a+b+c,我们将'+'写在 a 和 b 之间,然后再将'+'写在 a+b(一个结果、数)和 c 之间。但是现在,我们要当那 1% 的人了 O(∩_∩)O~
其实上面这种常见的 "放置操作符位置" 的方式或者说写法是有名称的,叫做 "中缀表达式",'缀'意味着 "操作符相对于操作数所放置的位置","中缀" 也就是 "操作符放在操作数的中间"。
相应的,肯定也存在前缀表达式和后缀表达式,即了操作符放在两个操作数的前面和后面的 "写法"。比如中缀表达式 a+b 的前缀写法是 + ab,后缀写法是 ab+。而 a+b+c 的前缀写法是 ++abc,后缀写法是 abc++。
注意,由于前缀、中缀、后缀表达式(以后可能略掉 "表达式" 三字)只不过是表达式的不同写法,所以某个中缀表达式必然存在效果、意义相同的前缀、后缀表达式(类似于用不同语言表达同一意思,如 who are you 和你是谁都是一个意思,但 "写法" 不一样)。而我们现在想要的,就是那个后缀表达式。为什么我们想要后缀表达式呢?因为后缀表达式相比于中缀表达式有一个非常重要的区别:
后缀表达式是从左向右 "依次计算",没有优先级的!!
而回顾我们之前所说,我们要找的正是一个没有优先级的等价的表达式,而没有优先级、等价这两点后缀表达式都可以做到。最关键的是,相比于将有优先级中缀表达式转换为无优先级中缀表达式,将一个中缀表达式转换为后缀表达式是比较简单的。同时,对后缀表达式进行计算也比较简单。而且,转换和计算都是利用栈的技术!
在我们讲解如何将中缀表达式转换为后缀表达式之前,我们先来说说对于一个后缀表达式,我们是如何计算的。首先我们已经知道了,计算后缀表达式需要一个栈,而现在我们可以确定的说,计算过程需要的是一个操作数栈,计算顺序就是:将后缀表达式从左到右依次遍历,如果当前元素为数字则入(操作数)栈,如果为操作符,则 pop 出栈顶两个元素(第一次 pop 出的是右操作数,第二次 pop 出的是左操作数)进行运算,然后将计算结果再次入栈,直至表达式结束,此时操作数栈内理应只剩一个元素即表达式结果。
比如,与 a+b 等价的 ab+,我们遇到 a,入栈
遇到 b,入栈
遇到'+',pop 得到 b 作为右操作数,再 pop 得到 a 作为左操作数(谁左谁右需要注意,减法、除法时弄反了结果将是错的),进行 a+b 运算,得出结果入栈
然后表达式到了结尾,所以 pop 出栈内唯一元素即结果。
再比如,与 a+b*c 等价的 abc*+,我们遇到 a,入栈
遇到 b,入栈
遇到 c,入栈
遇到'*',pop 出 c 作为右操作数,pop 出 b 作为左操作数,进行 b*c 运算后将结果入栈
遇到'+',pop 出 b*c 的结果(假设为 d)作为右操作数,pop 出 a 作为左操作数,进行 a+d 运算,然后将结果入栈
此时表达式结束,栈内只剩一个元素,即表达式结果。而且很显然的,这个结果是对的!
至此,我们已经确定了两件事情:
1. 中缀表达式必然存在后缀表达方法
2. 后缀表达式不存在优先级问题,只需利用栈进行 "从左至右依次计算" 即可
为了强化对后缀表达式计算方法的记忆(因为后面还有不少篇幅),我们再说一次后缀表达式的计算方法,就是:将后缀表达式从左到右依次遍历,如果当前元素为数字则入(操作数)栈,如果为操作符,则 pop 出栈顶两个元素(第一次 pop 出的是右操作数,第二次 pop 出的是左操作数)进行运算,然后将计算结果再次入栈,直至表达式结束,此时操作数栈内理应只剩一个元素即表达式结果。
其实前缀表达式也没有优先级问题,但是我们没有选择它,原因是实现中缀转换为前缀以及计算前缀表达式都不太符合我们的习惯,都是从右往左倒着来的╮(╯_╰)╭既然我们有符合习惯又不会更差的后缀表达式可用,那么我们就用后缀表达式喽~
既然现在我们已经知道了如何对后缀表达式进行计算,那么我们就可以先写出计算器程序中的一个模块来,也就是负责计算后缀表达式的模块,我们将其命名为 calculate()。至于获取输入、转换表达式,我们将它们作为其它模块,到时再处理。
- //两个表达式数组,Infix开头的暂存中缀表达式,Postfix开头的存储用于计算的后缀表达式
- Elem InfixExpression[SIZE];
- Elem PostfixExpression[SIZE];
- //用于计算后缀表达式的操作数栈,topNum指向操作数栈的栈顶(空位置,不是栈顶那个元素的位置)
- //栈内元素为double是因为int/int有可能得出小数
- double StackNum[SIZE];
- size_t topNum =0;
- //操作数栈的push
- voidpushNum(double e)
- {
- StackNum[topNum++] = e;
- }
- //操作数栈的pop
- double popNum()
- {
- returnStackNum[--topNum];
- }
- //虽然我们的结构体中使用的是int,但是int/int也有可能出现小数,所以我们返回值使用double
- double calculate()
- {
- //遍历后缀表达式数组,输出后缀表达式,没有特殊目的,只是方便我们"检查"一下后缀表达式
- for(size_t i =0;i < SIZE;++i)
- {
- if(!PostfixExpression[i].IsNum && PostfixExpression[i].oper =='=')
- {
- printf("%c\n",'=');
- break;
- }
- else if (PostfixExpression[i].IsNum)
- {
- printf("%d", PostfixExpression[i].num);
- }
- else
- {
- printf("%c", PostfixExpression[i].oper);
- }
- }
- //后缀表达式的计算过程,遍历整个后缀表达式数组,理论上我们中途会遇到'='跳出遍历,如果没有,好吧,程序要出错了
- for(size_t i =0;i < SIZE;++i)
- {
- //如果当前元素不是数字且其oper=='=',则说明表达式到末尾了,此时我们弹出栈内元素(理应为唯一一个)作为计算结果返回
- if(!PostfixExpression[i].IsNum&&PostfixExpression[i].oper =='=')
- {
- return popNum();
- }
- //如果当前元素为数字,则我们将其转换为double型并入栈
- else if (PostfixExpression[i].IsNum)
- {
- pushNum((double)(PostfixExpression[i].num));
- }
- //如果当前元素不是数字也不符合oper=='='就说明其是一个运算符(不会是括号,后缀表达式没有括号)
- //此时我们按计算方式pop出栈顶两元素进行计算并将结果重新压入栈
- else
- {
- //temp用于暂存栈顶两元素的计算结果
- doubletemp =0.0;
- //注意,第一次popNum得到的应作为右操作数,第二次popNum得到的作为左操作数,我们分别记为rear和front
- doublerear = popNum();
- doublefront = popNum();
- //根据当前元素选择应进行的运算,并将结果入栈
- switch (PostfixExpression[i].oper)
- {
- case '+':
- temp = front + rear;
- pushNum(temp);
- break;
- case '-':
- temp = front - rear;
- pushNum(temp);
- break;
- case '*':
- temp = front*rear;
- pushNum(temp);
- break;
- case '/':
- temp = front / rear;
- pushNum(temp);
- break;
- }
- }
- }
- //此处的return 0;只是为了防止编译器报错
- return 0;
- }
注意一下,上面的代码中有两个表达式数组,一个存储中缀表达式,一个存储后缀表达式,我们的 calculate() 只对后缀表达式数组进行操作,中缀表达式数组我们只是暂且先定义出来以备之后要用。
好了,现在我们已经能够处理后缀表达式了,接下来的问题就是如何由中缀表达式获得等价的后缀表达式。从程序设计的角度来说,最方便的方法当然是使用者直接键入后缀表达式,这样就只需要获取、处理输入,而不需要再进一步转换。但是这显然是不可能的,别想了╮(╯_╰)╭
我们之前说过,将中缀转换为后缀是很简单的,而且也是利用栈的技术,现在我们就来说说具体是如何利用栈来实现转换的。
首先,计算后缀表达式我们用到的栈是操作数栈,而转换中缀表达式我们需要的是一个操作符栈:
- //操作符栈,topOper指向操作符栈的栈顶(即栈中最上面那个元素的上面那个空位置)
- char StackOper[SIZE];
- size_t topOper =0;
- //操作符栈的push
- voidpushOper(char oper)
- {
- StackOper[topOper++] = oper;
- }
- //操作符栈的pop
- char popOper()
- {
- returnStackOper[--topOper];
- }
有了操作符栈后,我们可以来谈谈我们是如何将中缀表达式转换为后缀表达式的了,其实过程是 "固定" 的:
1. 遍历中缀表达式
2. 如果当前中缀元素为操作数,则直接将此操作数 "输出" 到后缀表达式尾端
3. 如果当前中缀元素为'*','/'或'(',直接 push 入操作符栈
4. 如果当前中缀元素为')',则依次 pop 出栈顶操作符、"输出" 到后缀表达式尾端,直至 pop 得到的是一个'('时停止,并丢弃该'('
5. 如果当前中缀元素为'+'或'-',则依次 pop 出栈顶操作符、"输出" 到后缀表达式尾端,直至栈底(栈空)或 pop 得到了一个'(',若 pop 得到一个'(',将'('重新 push 入栈。达到这两个条件之一后,将此操作符('+'或'-')入栈。
6. 如果当前中缀元素为'=',则依次 pop 出栈顶操作符、"输出" 到后缀表达式尾端,直至栈底(栈空)。
提醒一下,根据 4、5 两点,可以看出:只有遍历到')'才会将栈内的最上面那个'('弹出,其它操作符均不会使'('弹出。
现在让我们假设一个中缀表达式 a+b*(c-(d+e))=,然后追踪一下它转换为后缀表达式的过程:
首先遍历遇到 a,因为是操作数,所以直接输出至后缀表达式,接着遇到'+',因为栈空所以将其入栈
接着我们遇到了 b,同上,输出至后缀表达式,接着我们遇到'*',因为是'*'、'/'和'('中的一种,所以直接入栈
再接着,我们遇到了'(',同上,直接入栈,然后是操作数 c,直接输出至后缀表达式
下一步我们遇到了'-',于是我们 pop 出栈顶元素,发现其是'(',所以我们将'('重新 push 入栈,然后将'-'入栈。
接着我们又遇到了'(',根据规则 3,直接入栈。然后是操作数 d,根据规则 2,我们将其输出到后缀表达式
现在我们到了'+'处,因为 pop 出栈顶元素为'(',所以将'('重新 push,然后将'+'也 push 入栈。
再接着我们遇到了操作数 e,直接输出到后缀表达式
接下来我们遇到了一个')',按照规则 4,我们依次 pop 出栈顶操作符并输出到后缀表达式,直至 pop 得到的是'('(丢弃)。于是我们将栈顶的'+'输出到了后缀表达式,并丢弃了'+'下面那个'('
接着我们又遇到了一个')',再次依照规则 4,我们将'-'输出到了后缀表达式并丢弃了'-'下面那个'('
最后,我们遇到了'=',于是我们依次 pop 出栈内元素并输出至后缀表达式,直至栈底。
至此,我们完成了对 a+b*(c-(d+e))= 的转换!
有了上述理论和 "实践",现在我们可以开始着手实现我们程序中的转换模块了,我们先假定 InfixExpression[] 中已经有一个正确的中缀表达式,我们定义一个函数 translate(),其功能为将 InfixExpression[] 中的表达式转换为后缀表达式并存入 PostfixExpression[] 中,以供 calculate() 函数计算。
- //用于translate()的一些函数,负责栈操作
- //将中缀转换为后缀时,如果遇到操作符,那么我们需要对操作符进行判断然后决定相应的(栈)操作
- //下面这些函数就是当遇到不同操作符时调用的不同函数,用如其名
- //参数意义是"后缀表达式数组的当前尾端下标",因为*/(都直接入栈所以不需要该参数,=虽然需要知道当前后缀尾端下标,但不需要更改,因为转换已经要结束了
- //其他几个函数因为可能改变"后缀表达式数组的当前尾端下标",所以需要接收指针型参数
- voidIsAdd(size_t *j);
- voidIsSub(size_t *j);
- void IsMulti();
- void IsDiv();
- void IsLeft();
- voidIsRight(size_t *j);
- void IsEqual(size_t j);
- //translate()函数的定义,其用途说明在Calculator.h中
- void translate()
- {
- //遍历中缀表达式数组,将其中存储的中缀表达式转换为后缀表达式并存入后缀表达式数组
- //i为中缀表达式数组的"当前下标"(当前所判断的元素),j为后缀表达式数组的"当前下标"(输出到后缀的新元素应放入的位置),切记两者并不同步
- for(size_t i =0, j =0;i < SIZE;++i)
- {
- //若当前中缀(中缀表达式的简称)元素为数字则我们直接将其"输出"到后缀表达式
- if (InfixExpression[i].IsNum)
- {
- PostfixExpression[j].IsNum =true;
- PostfixExpression[j++].num = InfixExpression[i].num;
- }
- //若当前中缀元素不是数字,则我们需要根据其"值"决定应选择的栈操作,这里也是中缀下标i和后缀下标j不同步的原因产生之处
- else
- {
- switch (InfixExpression[i].oper)
- {
- case '(':
- IsLeft(); //当前元素为'('时,我们调用IsLeft(),因为'('必然是直接入栈,所以我们的j不会发生变化
- break;
- case ')':
- IsRight(&j);//当前元素为')'时调用IsRight(),因为')'可能导致输出元素至后缀表达式,所以需要知道后缀的下标j,并且j可能会发生变化,我们将j的地址传递过去
- break;
- case '+':
- IsAdd(&j);//当前元素为'+'时调用IsAdd(),因为'+'可能导致输出元素至后缀表达式,所以需要知道后缀的下标j,并且j可能会发生变化,我们将j的地址传递过去
- break;
- case '-':
- IsSub(&j);//当前元素为'-'时调用IsSub(),因为'-'可能导致输出元素至后缀表达式,所以需要知道后缀的下标j,并且j可能会发生变化,我们将j的地址传递过去
- break;
- case '*':
- IsMulti(); //当前元素为'*'时调用IsMult(),因为'*'直接入栈,所以j不会发生变化,不需要传递
- break;
- case '/':
- IsDiv(); //当前元素为'/'时调用IsDiv(),因为'/'直接入栈,所以j不会发生变化,不需要传递
- break;
- case '='://当前元素为'='时调用IsEqual(),因为'='会导致输出元素至后缀表达式,所以需要知道j
- IsEqual(j);
- return;
- }
- }
- }
- }
- //如果是'('则直接pushOper()
- void IsLeft()
- {
- pushOper('(');
- }
- //如果是')'则弹出栈顶元素直至栈顶元素为'(',当栈顶元素为'('时弹出并丢弃
- voidIsRight(size_t *j)
- {
- char oper;
- //如果是正确的表达式,则遇到)时栈内一定有(,此时循环条件其实没作用
- while(topOper >0)
- {
- //获取栈顶元素oper = popOper();
- //如果是'('则返回,因为'('被丢弃所以可以不理睬
- if(oper =='(')
- return;
- //如果不是'('则将该操作符"输出"至后缀表达式
- else
- {
- PostfixExpression[(*j)].IsNum =false;
- PostfixExpression[(*j)++].oper = oper;
- }
- }
- }
- //如果是'+'则依次pop栈顶操作符,直至pop所得为'('或栈为空,若pop得到'('需要将其重新push入栈
- //pop至上述两种情况之一后,将'+'入栈
- voidIsAdd(size_t *j)
- {
- char oper;
- while(topOper >0)
- {
- oper = popOper();
- if(oper =='(')
- {
- pushOper(oper);
- break;
- }
- else
- {
- PostfixExpression[(*j)].IsNum =false;
- PostfixExpression[(*j)++].oper = oper;
- }
- }
- pushOper('+');
- }
- //如果是'-'则依次pop栈顶操作符,直至pop所得为'('或栈为空,若pop得到'('需要将其重新push入栈
- //pop至上述两种情况之一后,将'-'入栈
- voidIsSub(size_t *j)
- {
- char oper;
- while(topOper >0)
- {
- oper = popOper();
- if(oper =='(')
- {
- pushOper(oper);
- break;
- }
- else
- {
- PostfixExpression[(*j)].IsNum =false;
- PostfixExpression[(*j)++].oper = oper;
- }
- }
- pushOper('-');
- }
- //'*'和'/'都直接入栈
- void IsMulti()
- {
- pushOper('*');
- }
- void IsDiv()
- {
- pushOper('/');
- }
- //如果是'=',则依次弹出栈顶元素输出至后缀表达式,直至栈空
- void IsEqual(size_t j)
- {
- char oper;
- while(topOper >0)
- {
- oper = popOper();
- PostfixExpression[j].IsNum =false;
- PostfixExpression[j++].oper = oper;
- }
- PostfixExpression[j].IsNum =false;
- PostfixExpression[j].oper ='=';
- }
至此,我们的整数四则运算计算器已经完成大半了,剩下没完成的就是负责获取输入并将输入存储进 InfixExpression[] 的模块了~ 由于该模块不属于栈的讨论范围,所以我们就不细说了,需要了解的读者可以看下述代码,也是有注释的哦~(另外,不支持使用者直接键入负数,比如 2+(-3)=,但支持这样的写法:2+(0-3)=)
- //get()函数的定义,get()的用处在Calculator.h头文件中
- bool get()
- {
- //用于保存用户输入的"字符"(还没有"翻译"称表达式的用户输入)
- charinput[SIZE *10];
- //输出提示信息,如果希望终止本程序则输入'n'printf("Please enter expression,end with '='\nIf you want to use negative numbers, please write like this:(0-1)\nIf you want to stop calculator,enter 'n':\n");
- //通过fgets函数获取用户输入fgets(input,sizeof(input) /sizeof(char), stdin);
- //简单判断,如果用户键入的是'n'则返回false,主程序会根据get()返回值决定程序走向
- if(input[0] =='n')
- return false;
- //若用户没有键入'n'则默认用户键入正确的中缀表达式
- //num用于"转换"用户输入的数字字符,具体用法见下
- intnum =0;
- //遍历整个input数组,当然,我们一般中途就会跳出
- for(size_t i =0, j =0;i < SIZE *10;i++)
- {
- //若当前字符为数字字符,则算出当前数字字符与其"左右"的数字字符一起组成了一个什么数
- if (isdigit(input[i]))
- {
- num = num *10+ input[i] -'0';//num表示"当前数字"(初始值为0),所以当"再次"遇到一个数字字符时,显然需要"当前数字"乘以10(进位)再加上新的数字字符对应的数字
- }
- //若当前字符不是数字字符,则我们需要判断其是什么字符
- else
- {
- //若当前字符为'='则表示表达式结束,此时我们需要进行一些特殊判断
- if(input[i] =='=')
- {
- //若表达式'='之前的那个字符不是')'则必然是一个数字字符,因此我们需要获取到那个数字字符与其"左右"数字字符组成的数
- if(input[i -1] !=')')
- {
- InfixExpression[j].IsNum =true;
- InfixExpression[j++].num = num;
- num =0;//获取完数字字符组成的数后,我们要将num重置以用于下一次"转换"数字字符
- }
- //无论'='前一个字符是数字字符还是')',我们都需要将'='存入中缀表达式数组并跳出对input[]的遍历InfixExpression[j].IsNum =false;
- InfixExpression[j++].oper ='=';
- break;
- }
- //'('是输入的又一特例,'('的前一个字符理应为运算符,所以我们不用也不该"获取"num的值
- else if(input[i] =='(')
- {
- InfixExpression[j].IsNum =false;
- InfixExpression[j++].oper ='(';
- }
- else if(input[i] ==')'&& input[i-1] ==')')
- {
- InfixExpression[j].IsNum =false;
- InfixExpression[j++].oper =')';
- }
- //除去上述特例,不论是运算符还是')',其前一个字符理应为数字字符,因此我们需要"获取"num的值,然后将操作符也存起来并重置num
- else
- {
- InfixExpression[j].IsNum =true;
- InfixExpression[j++].num = num;
- num =0;
- InfixExpression[j].IsNum =false;
- InfixExpression[j++].oper = input[i];
- }
- }
- }
- //以下循环为辅助性的,效果是输出中缀表达式中存储的表达式,理论上屏幕输出应与使用者输入相同
- for(size_t i =0;i < SIZE;++i)
- {
- if(!InfixExpression[i].IsNum&&InfixExpression[i].oper =='=')
- {
- printf("%c\n",'=');
- break;
- }
- else if (InfixExpression[i].IsNum)
- {
- printf("%d", InfixExpression[i].num);
- }
- else
- {
- printf("%c", InfixExpression[i].oper);
- }
- }
- //返回true告诉主程序用户没有键入'n'
- return true;
- }
另外,虽然本文中已经有了 "完整" 的计算器代码,但终究是片断的,而且没有包含头文件。如果想要查看完整项目代码,请前往
https://github.com/nchuXieWei/Simple-Calculator
最后的最后,提醒一句:虽然中缀表达式存在优先级问题,但并不意味着它不能用类似的方法求解!对中缀表达式进行求解依然是运用栈的技术。我们的计算器程序中使用了一个操作符栈用于转换,一个操作符数栈用于计算,而如果对中缀表达式进行求解则是同时利用操作数栈和操作符栈,有兴趣的同学可以去了解相关的算法。特意提醒的目的是不希望 "目光局限",这一点很多人很容易犯,就像我之前也一直 "默认" 表达式应该先转换为后缀表达式再求解,却没想过是否可以转换为前缀表达式,或者是否能直接对中缀表达式求解。我觉得保持一种 "探索" 的精神是非常有必要的,不仅仅是为了提升,有时候也会是一种乐趣!
来源: http://www.cnblogs.com/mm93/p/6702083.html