在前面的学习之中,我感觉对这个问题理解得不够透彻,随着一次又一次的理解,越来越明了了,所以再整理一下。

使用栈进行表达式计算

表达式计算,就是所谓的我们生活中常见的 1+5*(45+6)这类的式子

表达式计算的核心原理就是 ****中缀表达式转后缀表达式***,在我们平时见到的计算式中我们遇到的都是中缀表达式,例如 “1+45(3-2)” ,后缀表达式看起来陌生但是我们在计算起来采用的都是后缀表达式,根据运算符号的优先级,我们可以将前式转换成后缀表达式:“1 45 3 2 - * + ” 在处理后缀表达式表达式遵循的规律为 遇到符号,将符号前两个数进行符号所对应的运算。

中缀表达式和后缀表达式的转换

当然上面只是解决大概,还有很多细节待处理,中缀转后缀表达式需要遵守一定的规则,这是由运算符的优先级来和原表达式书写顺序决定,这一步可以由栈完成,处理方法是:(下面是中缀表达式转后缀表达式的算法描述)

我们准备一个栈来处理符号

  1. 逐个按中缀表达式的顺序处理每一个元素(符号和数)

  2. 遇到数值直接入追加到后缀表达式的尾部

  3. 遇到符号跟当前栈顶元素(当栈为空时,那么当前符号优先级大),如果栈顶符号优先级大,符号出栈追加到后缀表达式的尾,反之追加到后缀表达式的尾

  4. 重复123的过程直到中缀表达式字串处理完毕

优先级的表达

优先级,如何在计算机体现呢?我们是这样处理的 “从左到右 先乘除 后加减,先算括号里面的”,这句话其实无法完全反应优先级!我们再仔细分析一下我们日常计算的表达式中的优先级:

****计算先从左计算到右****:这句话可以描述成,****同一个运算符优先级也分左右,右运算符大于左运算符(相对操作数左右而言)****,比如1+2+3 ,我们是先计算1+1呢还是先计算2+3?答案是先计算1+2,为啥?其实这里旧隐藏了一个问题,同一个运算符也分左右,1+2中的+优先级比2+3中的高。(注:这里严格按照从左到右计算,无视交换律和结合律)

****去括号,先处理括号内部的运算****:其实这里也好理解,****让左括号的优先级比任何符号的优先级别高,同时让左括号的优先级小于右括号****,这样就可以优先计算括号内部的了。但是这里仅仅做到了优先计算括号内的,但是括号有没有对应的计算,我们需要将它去除。****其实将括号作为一个特例,左括号和右括号优先级相等,并且左括号不进入符号栈****,这样如果我们栈顶元素是右括号的时候,表明括号内部的已经优先处理,所以’(’出栈,不追加到后缀表达式尾。

先乘除再加减,这个就是本来的意即可。

至于前面所说的优先级,如何使用C语言表达出来呢?If or case语句?这一样像的太复杂了,我们完全可以使用数组保存一个对照表即可,如下

const char Prior[7][7] = {
  //   +    -   *    /  (   )   #
    {'>','>','<','<','<','>','>'},//+
    {'>','>','<','<','<','>','>'},//-
    {'>','>','>','>','<','>','>'},//*
    {'>','>','>','>','<','>','>'},// /
    {'<','<','<','<','<','=','$'},//(
    {'>','>','>','>','$','>','>'},//)
    {'<','<','<','<','<','$','='}// # 
};

确定表达式遍历已经结束

确定表达已经结束,简单的办法就是是否再处理\0,当然这个不是最优的方案?为了而我们能够处理“)5+1”这类的错误,我们在****中缀表达式开始和结尾加上 #作为休止符。****我们在处理优先级的时候规定 #比所有符号的优先级低,这样就不会干扰符号优先级,#与优先级相等,当我们遇到栈顶为#遍历符号为#的时候说明表达式已经结束。为了能够处理“)5+1”简单一点可以规定 #遇到)比较就出错。

浮点数字串转浮点数

其实这个调用C语言的函数atoi()即可,我们只需找到这个浮点数的开始和结束即可

错误处理

比如1/0 和“+1=%2”这类错误,我们可以使用c++的try catch语句抛出对应的错误即可。

实际流程

当然上述说明的是后缀表达式和中缀表达式的转化,当然这个方法很多,比如使用而二叉树就可以做到。在实际计算中,我们无需转换之后进行计算,我们完全可以边转换再计算:

- ****栈顶符号优先级大****: 新的操作符 没有旧的运算符高的时候 ,数据栈出栈提取两个操作数 进行旧的操作符运算 并且结果入数据栈 新符号入栈

- *栈顶符号优先级小* 符号入符栈

- *栈顶符号优先级等* 两个括号相遇 去括号 或者 表达运算结束

- 当栈顶和遍历符号都为# 表达计算完成

- 错误处理

表达式计算

具体代码

double expreetor(std::string str)throw (Exception)
{
  stack<int> OPTR; //符号栈
  stack<double> OPND;// 数值栈
  OPTR.push(isOperator('#'));//符号栈存入起始符
  str.push_back('#');//插入截至符号 
  double result = 0; //结果
  int i = 0, op1 = -1, op2 = -1;//遍历字串 和 新操作符 旧操作符
  char c = str[0];
  double num1 = 0, num2 = 0;//操作数
  std::string num;
  while (c != '#'||OPTR.top()!=6)//表达没有结束
  {
    if (c >= '0' && c <= '9')//得到操作数
    {
      while ((c >= '0' && c <= '9') || c == '.')
      {
        num.push_back(c);
        c = str[++i];
      }
      OPND.push(atof(num.c_str()));
      num.clear();
    }
    else//对符号进行处理
    {
      //取出操作符
      op1 = isOperator(c);
      op2 = OPTR.top();
      switch (pritor(op2, op1))
      {
      case '<'://符号入符栈 并且 处理下一个字符
        OPTR.push(op1);
        c = str[++i];
        break;
      case '='://取括号 符号栈出栈  并且 处理下一个字符
        OPTR.pop();
        c = str[++i];
        break;
      case '>'://数据栈出栈提取两个操作数  进行旧的操作符运算  并且结果入数据栈 新符号入栈
        if (OPND.size() < 2 || OPTR.size() < 1)
        {
          Exception e("表示式有误\n");
          throw e;
        }
        num1 = OPND.top();
        OPND.pop();
        num2 = OPND.top();
        OPND.pop();
        op2 = OPTR.top();
        OPTR.pop();
        result = cctor(op2, num2, num1);//注意!!num2 / - num1 取出的顺序式反的
        OPND.push(result);
        break;
      default:
        Exception e("表示式有误\n");
        throw e;
        break;
      }//switch
    }//else
  }
  return OPND.top();
}

本文由 越行勤 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://yingwiki.top/2021/07/04/stack-bdjs
最后更新于:  27  天前,内容可能已经不具有时效性,请谨慎参考。

Q.E.D.


努力学习的小菜鸟