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

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

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

#include 
#include 
#include 
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

测试：

input : 22*(1+2)-(3*4)/(2*1)
output :
22 1 2 + * 3 4 * 2 1 * / -
60

input : 1+3*(2+5)
output :
1 3 2 5 + * +
22

input : 1+3*((2+5)
output : terminate called after throwing an instance of 'std::invalid_argument' what(): too many left barckets!

input : 1+3*(2+5))
output : terminate called after throwing an instance of 'std::invalid_argument' what(): No left bracket match!

input : 1+3*(2+5)/0
output :
1 3 2 5 + * 0 / +
terminate called after throwing an instance of 'std::invalid_argument' what(): Divided by zero.

input : 1+3*(2++5)
output :
1 3 2 + 5 + * +
terminate called after throwing an instance of 'std::invalid_argument' what(): too many symbols.

参考：

1. 《C++ Primer》