2020-08-14 基于栈进行简单四则运算（带括号)

阳光穿透心脏的1/2处 2022-11-27 07:24 135阅读 0赞

## 前言： ##

本例程参考 《数据结构 C语言》版本内 表达式求值一例对于堆栈进行深入研究，后续由于进行重复计算，改用 vector 作为容器但在思维上依旧采用栈先入后出。  
核心就是通过当前符号与前一符号进行权重比较，选择计算，消去括号或则只写入符号不运算的方式。

#### 改进点： ####

1 原先将 前符号位 ) 都需进行运算，这样 )+ 这类实际是有问题改为 < 只填写符号(具体看程序)  
2 引入 \_third 值用于处理 )+2\# 这种情况，这是不需要计算的  
3 一次计算完成之后通过字符拼接重新构成一个字符串，思考逻辑通拆解计算的方式类似也是前后符号比较权重 combinationSymbol  
4 可以简单处理 () 关系，但暂时无法处理 ()) 数量不匹配等问题，可在计算完成之后，进行符号匹配检查  
5 输入的运算符号可以通过检查进行识别，暂未处理  
6 是应用上可按需调整

// CMakeStudio.cpp: 定义应用程序的入口点。
    //
    
    #include <iostream>
    #include <vector>
    #include <sstream>
    #include <string>
    #include <tuple>
    #include <optional>
    #include <functional>
    
    using namespace std;
    
    /**
     * \brief 判断前后运算符大小，对于 > 则进行计算 < 不处理 = 消去括号 J 表示结束 E 表示错误
     * \remark
     *     +      -      *      /      (      )      #
     * +   >      >      <      <      <      >      >
     * -   >      >      <      <      <      >      >
     * *   >      >      >      >      <      >      >
     * /   >      >      >      >      <      >      >
     * (   <      <      <      <      <      =      E
     * )   <      <      <      <      E      <      <
     * #   <      <      <      <      <      E      J
     *
     * \param _first
     * \param _second
     * \param _third 这个参数默认是 \0 是为了应对 )+2# 这种情况时，只需要按照 < 方式处理
     * \return
     */
    char getPrecede(const char& _first, const char& _second, char _third = '\0')
    {
           char res{ '%' };
    
           //对于 )+2# 这种情况做单独处理，不需要进行计算
           if ((_first == '+' || _first == '-' || _first == '*' || _first == '/') && 
    _second == '#' && ')' == _third) {
                  return '<';
           }
    
           if (_first == '+' || _first == '-') {
                  switch (_second)
                  {
                  case '+':
                  case '-':
                  case ')':
                  case '#':
                         res = '>'; break;
                  case '*':
                  case '/':
                  case '(':
                         res = '<'; break;
                  }
    
           }
           else if (_first == '*' || _first == '/') {
                  switch (_second)
                  {
                  case '(':
                         res = '<'; break;
                  default:
                         res = '>'; break;
                  }
           }
           else if (_first == '(') {
                  switch (_second)
                  {
                  case ')':
                         res = '='; break;
                  case '#':
                         res = 'E'; break;
                  default:
                         res = '<'; break;
                  }
           }
           else if (_first == ')') {
                  if (_second == '(') {
                         return 'E';
                  }
                  
                  return '<';
           }
           else if (_first == '#') {
                  switch (_second)
                  {
                  case '#':
                         res = 'J'; break;
                  case ')':
                         res = 'E'; break;
                  default:
                         res = '<'; break;
                  }
           }
    
           return res;
    }
    
    /**
     * \brief 专门用于供拼装字符串前后字符串关系判断
     * \remark 未标明表明为 >; E 表示异常 J 表示结束 但实际中可能并未使用该符号
     *     +      -      *      /     (      )      #
     * +                              <
     * -                              <
     * *                              <
     * /                              <
     * (                              <             E
     * )   <      <      <      <     E      <      J
     * #                              <      E      J
     * 
     * \param a1 前一个符号
     * \param a2 当前符号
     * \return char
     */
    char combinationSymbol(char a1, char a2)
    {
           if (a2 == '#') {
                  return '='; //结束
           }
    
           if (a2 == '(') {
                  return '<'; //只写符号
           }
    
           char res{ '\0' };
           if (a1 == ')') {
    
                  switch (a2) {
                  case '(':
                         res = 'E'; break; //异常
                  default:
                         res = '<'; break;
                  }
           }
           else {
                  res = '>'; //数值+符号
           }
    
           return res;
    }
    
    /**
     * \brief 获取栈顶数据
     * \param _stack
     * \return
     */
    char getTopValue(vector<char>& _stack)
    {
           return _stack.back();
    }
    
    /**
     * \brief 消去括号
     * \param _stack
     * \return
     */
    void handleBracket(vector<char>& _stack)
    {
           _stack.pop_back();
    }
    
    //公式计算 (这部分可以替换成想要的内容)
    optional<double> countVal(const double& _firstVal, const double& _secondVal, const 
    char& _symbol)
    {
           double res{ 0 };
           switch (_symbol)
           {
           case '*':
                  res = _firstVal * _secondVal; break;
           case '/':
                  if (0 == _secondVal) { //分母不能为 0 
                         return nullopt;
                  }
                  res = _firstVal / _secondVal; break;
           case '+':
                  res = _firstVal + _secondVal; break;
           case '-':
                  res = _firstVal - _secondVal; break;
           }
           return res;
    }
    
    /**
     * \brief 处理 前一个符号权限大于后一个符号, 并将计算结果重新放回栈中
     * \param _stack
     * \param _numStack
     * \return true 计算完成 false 计算失败
     */
    bool handleMoreThan(vector<char>& _stack, vector<double>& _numStack)
    {
           //至少确保有两个数字一个符号才可以进行运算
           //This function requires at least two number and one symbol for calculation
           if (_numStack.size() < 2 || _stack.size() < 1) {
                  return false;
           }
           //取出值
           double _secondVal = _numStack.back();
           _numStack.pop_back();
           double _firstVal = _numStack.back();
           _numStack.pop_back();
           char _symbol = _stack.back();
           _stack.pop_back();
    
           //计算结果并压入栈中 计算公式存在问题
           auto res = countVal(_firstVal, _secondVal, _symbol);
           if (!res) {
                  return false;
           }
    
           _numStack.push_back(res.value());
           return true;
    }
    
    
    
    /**
     * \brief 首尾加入 # 表示公式长度的范围 
     * \param _str [in] 传入参数
     * \param val  [out] 结果值
     * \return false 表示公式异常 true 表示公式正常; 返回 nullopt 代表计算完成
     */
    optional<pair<string, bool>> getFormula(const string& _str, double& val)
    {
           //所有公式都是以#作为结束符号
           string str = _str + "#";
    
           vector<double> opnd;
           vector<char> optr;
           optr.push_back('#');
    
           string tempNum{ "" }; //临时解析的数据内容
           char tempPtr{ '\0' }; 
           char tempThird{ '\0' };
    
           for (int i = 0, size = static_cast<int>(str.length()); i < size; i++) {
                  if (str[i] >= '0' && str[i] <= '9' || str[i] == '.') {
                         tempNum += str[i];
                  }
                  else {
                         if (tempNum != "") {
                               opnd.push_back(stod(tempNum));
                         }
    
                         tempPtr = str[i];
                         //用于处理 )+3# 这种情况
                         if ('#' == tempPtr && optr.size() > 1) {
                               tempThird = optr.at(optr.size() - 2);
                         }
                         else {
                               tempThird = '\0';
                         }
    
                         switch (getPrecede(getTopValue(optr), tempPtr, tempThird))
                         {
                         case '<':
                               optr.push_back(tempPtr); break;
                         case '=':
                               //消去括号
                               handleBracket(optr);
                               break;
                         case '>':
                               //计算
                               if (!handleMoreThan(optr, opnd)) {
                                      return make_pair("ERR", false);
                               }
                               optr.push_back(tempPtr);
                               break;
                         case 'J':
                               //结束单纯将 # 加入到最后
                               optr.push_back(tempPtr);
                               break;
                         case 'E':
                               return make_pair("ERR", false);
    
                         }
                         tempNum = "";
                  }
           }
    
           // 当符号清空或则 optr 内只有 ## 时认为计算完成，返回 over 和值
           if (optr.size() == 0) {
                  val = stod(_str);
                  return nullopt;
           }
           else if (optr.size() <= 2) {
                  val = opnd.back();
                  return nullopt;
           }
           //用于获取值的la
           function<string(vector<double>&)> getOPNDVal = [&](vector<double>& _stack) 
    {
                  double val = _stack.front();
                  _stack.erase(_stack.begin());
                  return to_string(val);
           };
    
           //重新构成一个字符串
           //主要是通过让当前符号与前一个符号进行比较进行堆加
           string tempStr{ "" };
           char c1 = optr.front();
           optr.erase(optr.begin());
           char c2;
           while (optr.size())
           {
                  c2 = optr.front();
                  optr.erase(optr.begin());
    
                  char testAA = combinationSymbol(c1, c2);
                  switch (testAA) {
                  case '<': //只添加当前符号
                         tempStr += c2; break;
                  case '>': //获取一个值并添加一个符号
                         if (opnd.size() > 0)
                               tempStr += getOPNDVal(opnd);
                         tempStr += c2; 
                         break;
                  case '=': //添加一个值
                         if (opnd.size() > 0)
                               tempStr += getOPNDVal(opnd);
                         break;
                  }
                  //比对过程中都是由当前值与前一个值进行比较，而当前值已经被移除，所以采用赋值方式传递
                  c1 = c2;
           }
           val = 0;
           return make_pair(tempStr, true);
    }
    
    
    
    int main()
    {
           string str = "1";
           while (cin >> str) {
                  double res{ 0 };
                  auto val = getFormula(str, res);
                  while (val) {
                         if (!val.value().second) {
                               break;
                         }
                         val = getFormula((*val).first, res);
                  }
                  if (val) {
                         if (!(*val).second) {
                               cout << "ERR" << endl;
                         }
                  }
                  else {
                         std::cout << res << endl;
                  }
           }
           return 0;
    }