四则运算第三版

相对于第二版又提出了新的要求

1.学生写的程序必须能判定用户的输入答案是否正确

2.程序必须能处理四种运算的混合算式

要求两人合作分析，单独编程，单独撰写博客

设计思路：

核心问题在于如何对随即产生的四则运算进行求值通过查阅资料和复习数据结构以及算符优先的概念发现可以采用中缀表达式转化为后缀表达式

并采用栈结构进行求值

  1 #include<iostream>
  2 #include<ctime>
  3 #include<string>
  4 #include<sstream> 
  5 #include "SqStack.h"
  6 using namespace std;
  7 
  8 char ops[7] = { '+', '-', '*', '/', '(', ')', '=' };
  9 char cmp[7][7] = { { '>', '>', '<', '<', '<', '>', '>' },
 10                     { '>', '>', '<', '<', '<', '>', '>' },
 11                     { '>', '>', '>', '>', '<', '>', '>' },
 12                     { '>', '>', '>', '>', '<', '>', '>' },
 13                     { '<', '<', '<', '<', '<', '=', ' ' },
 14                     { '>', '>', '>', '>', ' ', '>', '>' },
 15                     { '<', '<', '<', '<', '<', ' ', '=' } };
 16 
 17 bool IsOperator(char ch)
 18 {
 19     for (int i = 0; i < 7; i++)
 20         if (ch == ops[i])
 21             return true;
 22     return false;
 23 }
 24 char Compare(char ch1, char ch2)
 25 {
 26     int i, m, n;
 27     char priority;
 28     for (i = 0; i < 7; i++) { //找到相比较的两个运算符在比较矩阵里的相对位置
 29         if (ch1 == ops[i])
 30             m = i;
 31         if (ch2 == ops[i])
 32             n = i;
 33     }
 34     priority = cmp[m][n];
 35     return priority;
 36 }
 37 
 38 bool Compute(double x, char op, double y, double &z)
 39 {
 40     switch (op) {
 41     case '+':    z = x + y;
 42         break;
 43     case '-':    z = x - y;
 44         break;
 45     case '*':    z = x * y;
 46         break;
 47     case '/':    if (fabs(y) > 1e-7) {
 48         z = x / y;
 49         break;
 50     }
 51                 else
 52                     cout << "除数为0，出错！" << endl;
 53         return false;
 54     }
 55     return true;
 56 }
 57 
 58 bool ExpEvaluation(char *str, double &result)
 59 {
 60     double a, b, v;
 61     char ch, op;
 62     int temp, i = 0;
 63     SqStack <char> optr(20);     //创建运算符栈optr
 64     SqStack <double> opnd(20);   //创建运算数栈opnd
 65     optr.Push('=');
 66     ch = str[i++];
 67     while (ch != '=' || optr.Top() != '=') {
 68         while (ch == ' ')   //跳过空格
 69             ch = str[i++];
 70         if (IsOperator(ch)) {  //是7种运算符之一
 71             switch (Compare(optr.Top(), ch)) {
 72             case '<':         //栈顶运算符优先级低
 73                 optr.Push(ch);
 74                 ch = str[i++];
 75                 break;
 76             case '=':         //脱括号并接收下一字符
 77                 optr.Pop();
 78                 ch = str[i++];
 79                 break;
 80             case '>':         //栈顶运算符优先级高，退栈并将运算结果入栈
 81                 op = optr.Top();
 82                 optr.Pop();
 83                 b = opnd.Top();
 84                 opnd.Pop();
 85                 a = opnd.Top();
 86                 opnd.Pop();
 87                 if (Compute(a, op, b, v)) { //计算v = a <op> b
 88                     opnd.Push(v);
 89                     break;
 90                 }
 91                 else {
 92                     result = 0;
 93                     return false;
 94                 }
 95             }
 96         }
 97         else {    //是数字
 98             temp = ch - '0';    //将字符转换为十进制数
 99             ch = str[i++];
100             while (!IsOperator(ch) && ch != ' ') {
101                 temp = temp * 10 + ch - '0'; //将逐个读入运算数的各位转化为十进制数
102                 ch = str[i++];
103             }
104             opnd.Push(temp);    //数值入栈
105         }
106     }
107     result = opnd.Top();
108     return true;
109 }
110 
111 
112 
113 string IntToString(int & i)
114 {
115     string s;
116     stringstream ss(s);
117     ss << i;
118     return ss.str();
119 }
120 
121 
122 void checkcon0(int &num,string chnum)
123 {
124     while(num!=2&&num!=4)
125     {
126         if(chnum=="否")
127         {
128             num=2;
129         }
130         else if(chnum=="是")
131         {
132             num=4;
133         }
134         else
135         {
136             cout<<"输入不合法，请重新输入: ";
137             cin>>chnum;
138             cout<<endl;
139         }
140     }
141 }
142 void checkcon1(int &num1,string chnum)
143 {
144     while(num1!=1&&num1!=0)
145     {
146         if(chnum=="否")
147         {
148             num1=1;
149         }
150         else if(chnum=="是")
151         {
152             num1=0;
153         }
154         else
155         {
156             cout<<"输入不合法，请重新输入: ";
157             cin>>chnum;
158             cout<<endl;
159         }
160     }
161 
162 }
163 void check(int &num2,string chnum)
164 {
165     num2 = std::atoi(chnum.c_str() );
166     while(num2<=0)
167     {
168         cout<<"输入不合法，请重新输入: ";
169         cin>>chnum;
170         cout<<endl;
171         num2 = std::atoi(chnum.c_str() );
172     }
173 }
174 
175 int main()
176 {
177     //数据定义部分
178     srand((int)time(NULL));
179     int control[2],itemnum, num_max, num_min, num_num, bracket_num;
180     string chnum[5];
181     string express = "";
182     char symbol[4],c[20];;                    //随机计算符号数组
183     symbol[0] = '+';
184     symbol[1] = '-';
185     symbol[2] = '*';
186     symbol[3] = '/';
187 
188     //输入及判断部分
189     cout << "是否有乘除（是/否）：  ";
190     cin >> chnum[0];
191     checkcon0(control[0],chnum[0]);
192     cout << "是否有括号（是/否）：  ";
193     cin >> chnum[1];
194     checkcon1(control[1],chnum[1]);
195     cout << "数字最大取值：  ";
196     cin >> chnum[2];
197     check(num_max,chnum[2]);
198     cout << "数字最小取值：  ";
199     cin >> chnum[3];
200     check(num_min,chnum[3]);
201     cout<<"式子数量： ";
202     cin>>chnum[4];
203     check(itemnum,chnum[4]);
204 
205     string *item=new string[itemnum];
206     double *result = new double[itemnum];
207     double *uans = new double[itemnum];
208     int rightnum = 0;
209 
210     //算式生成部分
211     for (int count = 0; count<itemnum; count++)
212     {
213         num_num = rand() % 10;
214         string *str = new string[num_num];
215         if (num_num == 0 || num_num == 1)
216         {
217             count--;
218             continue;
219         }
220 
221         //定义并初始化动态数组 num:数字数组  symnum:符号选择数组  sym:符号数组
222         int *num = new int[num_num];
223         int *symnum = new int[num_num - 1];
224         char *sym = new char[num_num - 1];
225 
226         int bracket_leftposition, bracket_rightposition;
227         int *bracket_left_time = new int[num_num];           //定义左、右括号生成次数数组，下标为数字位置
228         int *bracket_right_time = new int[num_num];
229         string *bracket_left = new string[num_num]();        //定义左右括号字符串型数组
230         string *bracket_right = new string[num_num]();
231         for (int rcount = 0; rcount<num_num; rcount++)          //左、右括号生成次数初始化
232         {
233             bracket_left_time[rcount] = 0;
234             bracket_right_time[rcount] = 0;
235         }
236 
237         //给参与计算的数赋值(指定数值范围)
238         for (int cnum = 0; cnum<num_num; cnum++)
239         {
240             num[cnum] = rand() % (num_max - num_min + 1) + num_min;
241         }
242 
243         //随机生成式子的各个位置的符号
244         for (int snum = 0; snum<num_num - 1; snum++)
245         {
246             symnum[snum] = rand() % control[0];
247             sym[snum] = symbol[symnum[snum]];
248         }
249 
250 
251         if (control[1] == 0)
252         {
253             bracket_num = rand() % 7 + 1;
254             //生成括号次数
255             for (int bcount = 0; bcount<bracket_num; bcount++)
256             {
257                 bracket_leftposition = rand() % num_num;                //随机生成左右括号的位置
258                 bracket_rightposition = rand() % num_num;
259                 if ((bracket_leftposition >= bracket_rightposition)||((bracket_leftposition==0)&&(bracket_rightposition==num_num-1)))     //先剔除部分一次性在一个数左右同时生成左右括号和在整个式子前后生成式子的情况
260                 {
261                     continue;
262                 }
263                 bracket_left_time[bracket_leftposition]++;            //该位置数左括号生成次数+1
264                 bracket_right_time[bracket_rightposition]++;
265             }
266         }
267         for (int stnum = 0; stnum < num_num-2; stnum++)
268         {
269             if ((symbol[symnum[stnum]] == '/') && (symbol[symnum[stnum + 1]] == '/'))
270             {
271                 bracket_left_time[stnum]++;
272                 bracket_right_time[stnum + 1]++;
273             }
274         }
275         for (int snum = 0; snum < num_num ; snum++)
276         {
277             
278             if (bracket_left_time[snum] == 1)
279             {
280                 bracket_left[snum] = "(";
281             }
282             if (bracket_left_time[snum] == 2)
283             {
284                 bracket_left[snum] = "((";
285             }
286             if (bracket_left_time[snum] == 3)
287             {
288                 bracket_left[snum] = "(((";
289             }
290             if (bracket_right_time[snum] == 1)
291             {
292                 bracket_right[snum] = ")";
293             }
294             if (bracket_right_time[snum] == 2)
295             {
296                 bracket_right[snum] = "))";
297             }
298             if (bracket_right_time[snum] == 3)
299             {
300                 bracket_right[snum] = ")))";
301             }
302             for (int bpcount = 0; bpcount<num_num; bpcount++)            //再次扫描数字左右括号生成次数相等的情况并排除
303             {
304                 if (bracket_left_time[bpcount] == bracket_right_time[bpcount])
305                 {
306                     bracket_right[bpcount] = "";
307                     bracket_left[bpcount] = "";
308                 }
309             }
310         }
311 
312         //输出算式
313         for (int ph = 0; ph<num_num - 1; ph++)
314         {
315             cout << bracket_left[ph] << num[ph] << bracket_right[ph] << sym[ph];
316         }
317         cout << bracket_left[num_num - 1] << num[num_num - 1] << bracket_right[num_num - 1] << "= ";
318 
319         
320         for (int i = 0; i < num_num; i++)
321         {
322             int &temp = num[i];
323             str[i] = IntToString(temp);
324         }
325         for (int ph = 0; ph<num_num - 1; ph++)
326         {
327             express =express+bracket_left[ph]+str[ph]+bracket_right[ph]+sym[ph];
328         }
329         express = express + bracket_left[num_num - 1] +str[num_num - 1]+ bracket_right[num_num - 1];
330         item[count] = express+"=";
331         
332         strcpy(c, item[count].c_str());
333         ExpEvaluation(c, result[count]); //求表达式的值
334         
335         cin >> uans[count];
336         if (uans[count] == result[count])
337         {
338             rightnum++;
339             cout << "回答正确" << endl;
340         }
341         else
342         {
343             cout << "回答错误" << endl;
344             cout << "正确答案是  " << result[count] << endl;
345         }
346         
347 
348         express="";
349 
350         if (count == 29)
351         {
352             delete[]num;
353             delete[]symnum;
354             delete[]sym;
355             delete[]bracket_left_time;
356             delete[]bracket_right_time;
357             delete[]bracket_left;
358             delete[]bracket_right;
359             delete[]item;
360             delete[]str;
361             delete[]result;
362         }
363 
364     }
365     cout << "本次测试共答对 "<< rightnum <<" 道题"<< endl;
366 
367     system("pause");
368     return 0;
369 }

SqStack.h

 1 #ifndef _SQSTACK_H_
 2 #define _SQSTACK_H_
 3 //定义顺序栈类
 4 template <class ElemType>//声明一个类模板
 5 class SqStack
 6 {
 7 public://顺序栈类的各成员函数
 8     SqStack(int m = 100);
 9     ~SqStack();
10     void Clear();
11     bool Empty() const;
12     int Length() const;
13     ElemType & Top() const;
14     void Push(const ElemType &e);
15     void Pop();
16 private://顺序栈类的数据成员
17     ElemType *m_base;//基地址指针
18     int m_top;//栈顶指针
19     int m_size; //向量空间大小
20 };
21 //构造函数，分配m个结点的顺序空间，构造一个空的顺序栈。
22 template <class ElemType>
23 SqStack <ElemType>::SqStack(int m)
24 {
25     m_top = 0;
26     m_base = new ElemType[m];
27     m_size = m;
28 }//SqStack
29  //析构函数，将栈结构销毁。
30 template <class ElemType>
31 SqStack <ElemType>::~SqStack()
32 {
33     if (m_base != NULL) delete[] m_base;
34 }//~SqStack
35  //清空栈。
36 template <class ElemType>
37 void SqStack <ElemType>::Clear()
38 {
39     m_top = 0;
40 }//Clear
41  //判栈是否为空，若为空，则返回true，否则返回false。
42 template <class ElemType>
43 bool SqStack <ElemType>::Empty() const
44 {
45     return m_top == 0;
46 }//Empty
47  //求栈的长度。
48 template <class ElemType>
49 int SqStack <ElemType>::Length() const
50 {
51     return m_top;
52 }//Length
53  //取栈顶元素的值。先决条件是栈不空。
54 template <class ElemType>
55 ElemType & SqStack <ElemType>::Top() const
56 {
57     return m_base[m_top - 1];
58 }//Top
59  //入栈，若栈满，则先扩展空间。插入e到栈顶。
60 template <class ElemType>
61 void SqStack <ElemType>::Push(const ElemType &e)
62 {
63     if (m_top >= m_size) {            //若栈满，则扩展空间。 
64         ElemType *newbase;
65         newbase = new ElemType[m_size + 10];
66         for (int j = 0; j < m_top; j++)
67             newbase[j] = m_base[j];
68         delete[] m_base;
69         m_base = newbase;
70         m_size += 10;
71     }
72     m_base[m_top++] = e;
73 }//Push
74  //出栈，弹出栈顶元素。先决条件是栈非空。
75 template <class ElemType>
76 void SqStack <ElemType>::Pop()
77 {
78     m_top--;
79 }//Pop
80 #endif
81 #pragma once

团队成员：罗元浩、赵承圣（http://www.cnblogs.com/zzcs/）