《C++ Primer》练习9.52：使用栈实现四则运算

栈可以用来使用四则运算，是一个稍微有点复杂的题目，去学习了一下用栈实现四则运算的原理，用C++实现了一下。首先要把常见的中缀表达式改成后缀表达式，然后通过后缀表达式计算，具体的原理可以参考这位博主的文章：C语言数据结构篇——用栈实现四则运算，在数和运算符之间都加入了空格来进行分隔，方便后续的提取有效数据处理。

代码还有优化的地方，先记录一下吧：

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int getOperatorPriority(char &a)
{
  int res;
  if (a == '(')
    res = 0;
  else if (a == '+' || a == '-')
    res = 1;
  else if (a == '*' || a == '/')
    res = 2;
  else if (a == ')')
    res = 3;

  return res;
}
bool compareOperatorPriority(char &a, char &b)
{
  int a_res = getOperatorPriority(a);
  int b_res = getOperatorPriority(b);
  return a_res >= b_res;
}

string createBackSeq(string &str)
{
  stack<char> sak;
  string str2;
  int seen = 0;
  int p = 0;
  for (int i = 0; i != str.size(); ++i)
  {
    if (isdigit(str[i]))
    {
      str2.append(str.substr(i, 1));
      if ((i + 1 != str.size() && !isdigit(str[i + 1])) || i == str.size() - 1)
        str2.append(" ");
    }

    else
    {
      if (sak.empty())
      {
        if (str[i] == '(')
          seen += 1;
        sak.push(str[i]);
      }
      else if (str[i] == ')')
      {
        if (seen != 0)
        {
          while (sak.top() != '(')
          {
            str2 += sak.top();
            str2.append(" ");
            sak.pop();
          }
          sak.pop();
          seen--;
        }
        else
          throw std::invalid_argument("No left bracket match!");
      }
      else
      {
        if (compareOperatorPriority(sak.top(), str[i]))
        {
          if (str[i] == '(')
          {
            seen++;
            sak.push(str[i]);
          }

          else
          {
            str2 += sak.top();
            str2.append(" ");
            sak.pop();
            sak.push(str[i]);
          }
        }
        else
        {
          sak.push(str[i]);
        }
      }
    }
  }
  while (!sak.empty())
  {
    if (seen != 0)
      throw invalid_argument("too many left barckets!");
    str2 += sak.top();
    str2.append(" ");
    sak.pop();
  }
  return str2;
}

int calculate(string &str)
{
  size_t pos1 = 0;
  size_t pos2 = 0;
  stack<int> b;
  while (pos2 != string::npos)
  {
    pos1 = str.find_first_not_of(' ', pos1);
    pos2 = str.find_first_of(' ', pos2);

    if (pos2 != string::npos)
    {
      string temp = str.substr(pos1, pos2 - pos1);
      if (temp.find_first_not_of("0123456789") == string::npos)
        b.push(stoi(temp));
      else
      {
        if (b.size() < 2)
          throw std::invalid_argument("too many symbols");
        int right = b.top();
        b.pop();
        int left = b.top();
        b.pop();
        int res;
        if (temp == "+")
          res = left + right;
        else if (temp == "*")
          res = left * right;
        else if (temp == "-")
          res = left - right;
        else if (temp == "/")
        {
          if (right == 0)
            throw std::invalid_argument("Divided by zero.");
          res = left / right;
        }

        b.push(res);
      }
      pos2 += 1;
      pos1 = pos2;
    }
  }
  return b.top();
}

int main()
{
  string str;
  string str2;
  str = "22*(1+2)-(3*4)/(2*1)";
  str2 = createBackSeq(str);
  cout << str2 << endl;
  cout << calculate(str2) << endl;

  str = "1+3*(2++5)";
  str2 = createBackSeq(str);
  cout << str2 << endl;
  cout << calculate(str2) << endl;	

  return 0;
}

测试：

参考：

1. 《C++ Primer》