一、实验目的、内容

输入是一个带有括号的四则运算表达式，输出是计算得出的正确计算结果。

二、实验程序设计及结构

1.需求分析

由于待求值表达式长度不限，故采用标准库类型string存储字符串；又因为运算符个数不确定，故采用标准库类型vector存储运算符的位置。要能检查错误，故包含math.h头文件利用宏定义NAN返回错误值。要能计算小数，故采用double作运算。

变量

字符串a(string)用于存储待求值表达式；数result(double)用于存储结果。

函数

计算函数double cal(string s)，主函数int main()，string的成员函数，vector的成员函数以及库函数stod、isnan和to_string。

2.设计结构或流程图

1. 输入表达式存入a中。
2. 调用计算函数求值，并存入b中。
   1. 输入表达式存入a中。
   2. 调用计算函数求值，并存入b中。
      1. 首先遍历字符串，若存在' '、'\t'则删除之以免影响后面的计算；若存在'('，将此时的位置保存于string类下的迭代器a中，n表示嵌套'('的个数递增；若存在')'，n递减，如果n减至0，递归调用计算函数以消除括号；若出现数字、运算符字符、小数点'.'以及指数'e'以外的字符或分母为0的情况，返回NAN。
      2. 在递归完成后（没有'('），如果n（左括号个数减右括号个数）非零，返回NAN。
      3. 处理乘除：定义向量u(vector<string::size_type>)保存'*'和'/'运算符的位置。从第一个运算符开始把相邻两个数用stod转换为double作运算，用to_string把运算结果转换为字符串用成员函数replace替换回原来的字符串，删除u的首元素并移动u中各元素的位置。重复上述过程直到u为空集。
      4. 处理加减：利用上面的u保存'+'和'-'运算符的位置，并将相邻的加减号合并。其余过程与乘除类似。
      5. 将结果转换为double并返回。
3. 判断b的值并输出。

三、设计过程

#include <iostream>
#include <string>
#include <vector>
#include <math.h> //利用宏定义NAN
using namespace std;
double cal(string s)
{string s1;string::iterator a, b, i; // a记录'(',b记录')'string::size_type n = 0;int l;if (false)F:s.replace(a, i + 1, to_string(cal(string(a + 1, i))).c_str()); // 递归计算括号
R:i = s.begin();while (i < s.end()){if (*i == ' ' || *i == '\t'){s.erase(i);goto R;}if (*i == '('){ // 防止悬垂else问题if (!n++)a = i;}else if (*i == ')'){ // 防止悬垂else问题if (!--n)goto F;}else if (*i != '\0' && *i != '.' && *i != 'e' && *i != '*' && *i != '-' && *i != '+' && *i != '/' && (*i < '0' || *i > '9') || (*i == '/' && *(i + 1) == '0' && *(i + 2) != '.'))return NAN; // 不是数学表达式++i;}if (n)return NAN; // 左括号个数不等于右括号个数vector<string::size_type> u;// k用作bool数组// 第一位表示第一个数字的正负性// 第二位表示第二个数字的正负性// 第三位表示第一个数字是否为字符串首个数字unsigned char k = 0;// 计算乘除for (b = a = s.begin(); a < s.end(); ++a)if (*a == '*' || *a == '/')u.push_back(a - b);while (u.size()){i = a = b = s.begin() + u[0];while ((*--b >= '0' && *b <= '9') || *b == '.' || *b == 'e')if (b == s.begin()){k = 4;goto G;}// n记录第一个数字的首位的位置k += *b == '-';if (*b == '-')n = b - s.begin();elsen = ++b - s.begin();G:double t = stod(string(b, a++));doif (++a == s.end())break;while ((*a >= '0' && *a <= '9') || *a == '.' || *a == 'e');double w = stod(string(i + 1, a));k += (w < 0) * 2;if (*i == '*'){l = (s1 = to_string(t * w)).size() - (a - b);s.replace(b, a, s1.c_str());}else if (w){l = (s1 = to_string(t / w)).size() - (a - b);s.replace(b, a, s1.c_str());}elsereturn NAN; // 除数为0switch (k){case 2:s.erase(s.begin() + n - 1);break; // 删除-号前的+case 3:s.insert(s.begin() + n, '+'); // 在计算结果之前加一个+}u.erase(u.begin());for (auto &q : u)q += l;}// 计算加减
H:for (a = (b = s.begin()) + 1; a < s.end(); ++a)if (*a == '+'){if (*(a + 1) == '-' || *(a + 1) == '+'){s.erase(a);goto H;}u.push_back(a - b);}else if (*a == '-'){if (*(a + 1) == '-'){s.replace(a, a + 2, "+");goto H;}else if (*(a + 1) == '+'){s.erase(a + 1);goto H;}u.push_back(a - b);}while (u.size()){i = a = (b = s.begin()) + u[0];double t = stod(string(b, a++));doif (++a == s.end())break;while ((*a >= '0' && *a <= '9') || *a == '.' || *a == 'e');if (*i++ == '+')l = (s1 = to_string(t + stod(string(i, a)))).size() - (a - b);elsel = (s1 = to_string(t - stod(string(i, a)))).size() - (a - b);s.replace(b, a, s1.c_str());u.erase(u.begin());for (auto &q : u)q += l;}return stod(s);
}
int main()
{string a;cout << "请输入数学算术表达式:\n";cin >> a;double result = cal(a);if (isnan(result))cout << "表达式不正确!\n";elsecout << result << endl;system("pause");return 0;
}

四、测试分析

第一组

第二组

实验中出现的bug及解决方案

bug	解决方案
u如果使用vector<string::iterator>在替换后可能导致u中的迭代器失效	使用数字而非迭代器保存
29行需要加上*i!='\0'，否则无论输入任何表达式都会报错	加上条件判断
容易出现超级大数	检查乘除时负负得正的情况，并在结果前加一个'+'用以区分；在每次替换完成后移动u中的元素

五、设计的特点和结果

采用递归的思想解决括号，并根据优先级和结合方向逐个处理运算符。

结果：求出表达式的值。