【数据结构】计算器的实现--栈的实战

计算器的实现--栈的实战

  

大家好啊，我是新来的小编~此处应有欢迎声~~

  今天是第一天上班，给大家带来的是《计算器的实现------栈的实战》。

  大家有没有和小编一样小时候的计算能力很差，被各种计算折磨的晕头转向?到后来，我发现了计算器这样神奇的东西，哇，真的是救我于水火之中。我因此潇洒了一两年的时间（此处应有归零声音响起）。

  不过快乐并不长久，学校开始要求进行多个数的加减乘除并且还涉及到大中小括号的四则运算，家里的老式计算器不好使了。9+（3-1）*3+10/2，这么简单的式子，计算器完全没有办法计算，幸好自己存了一点私房钱，买了一个高级一点的计算器，引入了四则运算表达式和括号。

老式计算器对于两个的运算原理大家都会进行，那么你有没有想过现在新式的计算器他是如何实现对数学表达式的求值呢？

  在讨论这个问题之前，让我们来了解一种全新的数据结构---栈（Stack）。

栈

  首先让我们来举一个例子，弹夹式手枪，我想大家一定都在电视上面见过甚至很多同学肯定都还玩过，那么弹夹中的子弹射出来的先后顺序你们有没有想过呢？对的，是先射出后面的子弹然后再射出前面的子弹，想要射出前面的子弹就必须要先射完后面的子弹。

觉得这个例子不够形象？那让我们再看一个例子。在使用APP时，大家一定都用过返回键吧？它是不是优先返回到前一步，而不是返回到前前步，或者前前前步？

上述例子的原因究竟是什么呢？就是因为它们用到了一种叫做栈的数据结构。

栈（stack）是限定仅在表尾进行插入和删除的线性表。

在通常情况下，我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（botton），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out)的线性表，简称为LIFO结构。

首先你要明确栈是一个线性表，栈的元素具有线性结构，即前驱后继关系，只不过他是一种特殊的线性表，他的插入和删除只能发生在栈顶而不是发生在其他的位置。

栈的插入我们叫做进栈，栈的删除我们叫做出栈。

简单的介绍了栈这种结构之后，现在让我们回到我们最初的问题，如何实现计算器的各种功能。

现在大家来看一看一个多项计算表达式，比如：“9+（5-1）*2+16/2”，仔细观察我们会发现，括号都是成对出现的，由左括号就一定会有右括号，对于多重括号，最终也是完全嵌套匹配的。这用栈结构正好合适，只要碰到左括号，就入栈，不管表达式有多少重括号，反正遇到左括号就进栈，而后面出现右括号时，就让栈顶的左括号出栈，期间让数字运算，这样，最终右括号的表达式从左到右巡查一遍，栈应该是由空到有元素，最终再因全部匹配成功后成为空栈。

逆波兰表达式

解决了括号的问题还不够啊，因为括号只是四则运算的一小部分，先乘除后加减使得问题依旧复杂，怎么办呢？波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年提出了一种不需要括号的后缀表达式，我们也把它称为逆波兰（Rever Polish Notation，RPN）表示。为啥叫这个名字呢？我觉得可能是因为这位逻辑学家的名字太复杂？Hh~~这也告诉我们呀，想要流芳百世，名字必须要取的好~~

让我们用刚开始的例子来分析一下逆波兰表达式，对于“9+（5-1）*2+16/2”，如果变成逆波兰的样子，应该为“9 5 1 - 2 * + 16 2 / +”，看见这个变化大家肯定对于后缀表达式这个名字的理解又深化了一些吧？其实就是所有的符号都是在要运算数字的后面出现。这里的括号不见了，同学们看起来肯定一点也不习惯，不过没关系，咱们聪明的计算机喜欢。

为了更好的给同学们解释逆波兰表达式的好处，我们现在来看看计算机如何运用它来计算出来最终结果的。

如何计算

后缀表达式：9 5 1 - 2 * + 16 2 / +

规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈进行运算，运算结果再进栈，一直带最终获得结果。

1：初始化一个空栈。此栈用来对要运算的数字进出使用，如图所示

2：后缀表达式的前三个元素都是数字，直接进栈

3：接下来是“-”，所以将1出栈作为减数，5出栈作为被减数，并运算得到4，再将4进栈

4：接着是2入栈

5：后面是“*”，也就意味着栈中的4,2出栈。得到8，然后将8进栈

6：下面是“+”，所以将8和9出栈相加得到17，再进栈

7：接着16和2进栈

8：接下来是“/”，因此，栈顶的2和16出栈，16和2相除得到8,8进栈

9：最后一个符号是“+”，所以8和17出栈并相加得到25，将25进栈

10：最后将25出栈，栈变为空。

很快，我们就解决了计算的问题，但是似乎，还有一个更重要的问题我们没有解决啊，怎么样将中缀表达式转换成后缀表达式呢？

下面让我们来了解一下如何将中缀表达式转为后缀表达式。

如何转换

目的，将9+（5-1）*2+16/2转变为9 5 1 - 2 * + 16 2 / +

  规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分;若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，直到最终输出后缀表达式为止。

 1：初始化一个空栈，用来对符号进出栈使用。

2：第一个字符是数字9，输出9，后面的是符号“+”，进栈。

3：第三个符号是“（”，依然是符号，因为他是左括号，还没有完成配对，进栈，如图所示。

4：第四个字符是5，输出，总表示为9 5，接着是“-”，进栈。

5：接下来是数字1，输出，表达式变为9 5 1，后面是“）”，此时，我们需要去匹配此前的“（”，所以栈顶依次出栈，并输出，直到“（”出栈为止，此时左括号上方只有“-”，因此输出“-”，表达式变为9 5 1 -。

6：紧接着是“*”，因为此时的栈顶符号是“+”，优先级低于“*”,因此不输出，“*”进栈，接着是数字2，输出，表达式变为9 5 1 - 2，

7：之后是符号“+”，此时当前栈顶元素“*”比这个“+”的优先级高，因此栈中的元素出栈并输出（没有比“+”更低的优先级，所以全部出栈），总输出表达式为9 5 1 - 2 * +。然后将“+”入栈，

8：紧接着是数字16，输出，表达式变为9 5 1 - 3 * + 16.后面是符号“/”，入栈。

9：最后一个数字是2，输出。

 10：因为已经到了最后，所以此时我们将栈里面的所有元素出栈并输出。最终表达式变为9 5 1 - 2 * + 16 2 / +。

关键点

经过上面的介绍，我们可以得出要想让我们的计算机具有处理我们通常的标准（中缀）表达式的能力，关键在于两个步骤。

 1：中缀变后缀（栈用来进出运算的符号）

2：计算后缀（栈用来进出运算的数字）

看了以上的介绍，我想大家一定都迫不及待的想见一见计算器的代码了，准备好，他来了。

代码

#includeusing namespace std;int top;int j = 2;int k = 0;class date {  public:  double a = -1;  //double是因为会出现小数，设为-1是为了方便判断  char m=NULL;}b[99], c[99], d[99];//生成栈，并初始化栈,这里生成三个栈，分别用于获得元素，储存符号，储存数字void getdate()//获取元素 {  char q;  int i = 0;  while ((q = getchar()) != '\n')//这里需要用getchar，因为是输入的字符 {    if (i == 0)//第一个元素要单独拿出来 {      if (q != '0')      b[i].a = q - '0';      //一个小技巧，将字符’n’转变为整数n else {        cout << "error date";        return;      }    } else    if (q >= '0' && q <= '9')    if (b[i-1].a >=0)  //判断一个数是几位数 {      b[i - 1].a = b[i - 1].a * 10 + (q - '0');      //多位数应该如何储存      i--;    } else    b[i].a = q - '0'; else    b[i].m = q;    i++;  }  top = i - 1;  //栈顶top所在的位置应该为i-1}void sort()//进行中缀表达式转化为后缀表达式 {  for (int i = 0 ;i <= top; i++) {    if (b[i].a >= 0) {      d[k].a = b[i].a;      k++;    } else    if (j == 2) {      c[j].m = b[i].m;      j++;    } else    if (b[i].m == '(') {      c[j].m = b[i].m;      j++;    } else    if (b[i].m == ')') {      d[k++].m = c[--j].m;      c[j].m = NULL;      c[--j].m = NULL;    } else if (c[0].m == '*' || c[0].m == '/') {      d[k++].m = c[--j].m;      d[k++].m = c[--j].m;      c[j].m = b[i].m;    } else    c[j++].m = b[i].m;  }  while ((j - 1) != 1)  d[k++].m = c[--j].m;}void calculate() {  double q[11] ;  int o = 2;  //为何设为2？因为在后面有o-2，在编译时系统会自动认为输入了-2，无法通过编译  q[0] = 1;  q[1] = 1;  k--;  for (int i = 0; i <= k; i++)  if (d[i].a != -1) {    q[o] = d[i].a;    o++;  } else {    switch (d[i].m) {      case '+': {        q[o - 2] = q[o - 2] + q[o - 1];        o--;        break;      }      case '-': {        q[o - 2] = q[o - 2] - q[o - 1];        o--;        break;      }      case '*': {        q[o - 2] = q[o - 2] * q[o - 1];        o--;        break;      }      case '/': {        q[o - 2] = (q[o - 2]*1.0) / q[o - 1];        o--;        break;      }      //*1.0是为了防止直接将分数转变为整数    }  }  if (--o == 2) {    cout << "你想要保留的小数位为？";    int z;    cin >> z;    cout << "经过计算你的结果为  " <q[2];  }  void main() {    cout << "这是一个计算器，请输入你需要计算的式子" << endl;    getdate();    sort();    calculate();  }

最终成果图~~

本次的推文就到此结束啦，希望各位看客老爷能够有所收获！

参考书籍程杰《大话数据结构》