中缀表达式求值(C++实现)

当初的数据结构上机作业，题目很奇葩，要求先将中缀表达式转换成后缀表达式再求值。

只加入了一些错误判断，因为输入的错误形式太多了，做到一半懒得做了。

代码：
展开

1 // 中缀表达式求值(通过先转换为后缀表达式再求值)
  2  // 作者:王锦
  3  // 邮箱:jinksw@vip.qq.com
  4  
  5  #include "stdafx.h"
  6  #include <stack>
  7  #include <queue>
  8  #include <iostream>
  9  #include <sstream>
 10  using namespace std;
 11  
 12  class IEcalculator//中缀表达式求值
 13  {
 14      private:
 15      stack<double> s;
 16      queue<string> suffixE;//用于存储后缀表达式序列
 17      stack<char> operatorStack;
 18      bool flag;//用于记录是否发生错误，避免不必要的计算
 19      bool aIsNotLessThenB(char a,char b);//用于判断a的优先级是否大于等于b
 20      bool getTwoOperands(double &opd1,double &opd2);
 21      bool compute(char op);
 22      void clear()//清除栈中元素
 23      {
 24          while(!s.empty())
 25              s.pop();
 26          while(!suffixE.empty())
 27              suffixE.pop();
 28          while(!operatorStack.empty())
 29              operatorStack.pop();
 30      }
 31      void calculateSE();
 32  public:
 33      void calculate();
 34  };
 35  bool IEcalculator::getTwoOperands(double &opd1,double &opd2)
 36  {
 37      if(s.empty())
 38      {
 39          cerr << "操作数缺失，请检查输入表达式！" << endl;
 40          return false;
 41      }
 42      opd1 = s.top();
 43      s.pop();
 44      if(s.empty())
 45      {
 46          cerr << "操作数缺失，请检查输入表达式！" << endl;
 47          return false;
 48      }
 49      opd2 = s.top();
 50      s.pop();
 51      return true;
 52  }
 53  
 54  bool IEcalculator::compute(char op)
 55  {
 56      double opd1,opd2;
 57      if(getTwoOperands(opd1,opd2))
 58      {
 59          switch (op)
 60          {
 61          case '+':
 62              s.push(opd2 + opd1);
 63              break;
 64          case '-':
 65              s.push(opd2 - opd1);
 66              break;
 67          case '*':
 68              s.push(opd2 * opd1);
 69              break;
 70          case '/':
 71              if(abs(opd1) < 1E-7)
 72              {
 73                  cerr << "除数不能为0，请检查表达式" << endl;
 74                  clear();
 75                  return false;
 76              }
 77              s.push(opd2 / opd1);
 78              break;
 79          default:
 80              break;
 81          }
 82      }
 83      else
 84      {
 85          clear();
 86          return false;
 87      }
 88  }
 89  
 90  void IEcalculator::calculateSE()
 91  {
 92      string expressionStream;
 93      while(!suffixE.empty())
 94      {
 95          expressionStream+=" "+suffixE.front();
 96          suffixE.pop();
 97      }
 98      expressionStream += "=";
 99      istringstream iss(expressionStream,istringstream::in);//将expressionStream作为输入流
100      char c;
101      double newOperand,result;
102      bool isRight = true;//compute(c)函数返回标志，若出现除数为0错误，则不再计算
103      while(iss >> c, isRight && c != '=')
104      {
105          switch (c)
106          {
107          case '+':
108          case '-':
109          case '*':
110          case '/':
111              isRight = compute(c);
112              break;
113          default:
114              iss.putback(c);
115              iss >> newOperand;
116              s.push(newOperand);
117              break;
118          }
119      }
120      if(isRight)
121      {
122          result = s.top();
123          s.pop();
124          if(s.empty())
125              cout << "result = " << result << endl;
126          else
127          {
128              cerr << "表达式操作数剩余！" << endl;
129          }
130          clear();
131      }
132      else
133      {
134          clear();
135      }
136  }
137  bool IEcalculator::aIsNotLessThenB(char a,char b)
138  {
139      switch (a)
140      {
141      case '(':
142          return true;
143      case '+':
144      case '-':
145          switch (b)
146          {
147          case '(':
148          case '*':
149          case '/':
150              return false;
151          default:
152              return true;
153              break;
154          }
155      case '*':
156      case '/':
157          switch (b)
158          {
159          case '(':
160              return false;
161          default:
162              return true;
163              break;
164          }
165      default:
166          break;
167      }
168  }
169  void IEcalculator::calculate()
170  {
171      flag = true;
172      double newOperand;
173      string tempStr = "";//用于将字符转换为字符串
174      char c;
175      while(cin >> c,c != '=' && flag)
176      {
177          switch (c)
178          {
179          case '+':
180          case '-':
181          case '*':
182          case '/':
183              while(!operatorStack.empty() && aIsNotLessThenB(operatorStack.top
184  
185  (),c) &&operatorStack.top() != '(')
186              {
187                  suffixE.push(operatorStack.top()+tempStr);
188                  operatorStack.pop();
189              }
190              operatorStack.push(c);
191              break;
192          case '(':
193              operatorStack.push(c);
194              break;
195          case ')':
196              while(!operatorStack.empty() && operatorStack.top() != '(')
197              {
198                  suffixE.push(operatorStack.top()+tempStr);
199                  operatorStack.pop();
200              }
201              if(operatorStack.empty())//此时栈空则错误
202              {
203                  flag = false;
204                  clear();
205                  break;
206              }
207              operatorStack.pop();
208              break;
209          default:
210              cin.putback(c);
211              cin >> newOperand;
212              string str;
213              stringstream ss;
214              ss<<newOperand;
215              ss>>str;
216              suffixE.push(string(str));
217              break;
218          }
219      }
220      while(!operatorStack.empty())
221      {
222          if(operatorStack.top() == '(')
223          {
224              flag = false;
225              break;
226          }
227          suffixE.push(operatorStack.top()+tempStr);
228          operatorStack.pop();
229      }
230      if(flag)
231      {
232          calculateSE();
233      }
234      else
235          cerr << "表达式输入有误，请重试" << endl;
236      clear();
237  }
238  
239  int _tmain(int argc, _TCHAR* argv[])
240  {
241      cout << "请输入中缀表达式,以=结束:(q退出)" << endl;
242      char c;
243      cin >> c;
244      while(c != 'q')
245      {
246          cin.putback(c);
247          IEcalculator test;
248          test.calculate();
249          cout << "请输入中缀表达式,以=结束:(q退出)" << endl;
250          cin >> c;
251      }
252      
253  }

原文链接: https://www.cnblogs.com/jinks/archive/2013/04/26/3044937.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍