【题目】
给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右括号，返回公式的计算结果。
【举例】
str = "48*((70-65)-43)+8*1"，返回 - 1816。
str = "3+1*4"，返回7。
str = "3+(1*4)"，返回7。
【说明】
1．可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。
2．如果是负数，就需要用括号括起来，比如"4*(-3)"。但如果负数作为公式的开头或括号部分的开头，则可以没有括号，比如"-3*4"和"(-3）*4"都是合法的。
3．不用考虑计算过程中会发生溢出的情况
【解题】
一般是使用栈，因为栈处理括号问题很好
1、没有括号存在
使用栈：
首先使用栈对字符串str进行分解
当遇到数字，则数据开始，云算符结束，当遇到运算符，数据结束，字符开始
然后进行数据和运算符入栈，当栈顶为‘*’或‘ / ’时，将栈顶的运算符和下面的 那个数据拿出来与目前的数据进行运算，然后得到的结果压入栈中。
然后当字符串数据压入完毕，然后依次从栈出弹出数据以及运算符，进行运算即可
2、存在括号
定义函数fun(str, index)
表示计算从index开始的字符串数据，知道遇到右括号或者字符串尾部结束，即fun中实现的就是一个简单的括号内部无括号的运算操作
【代码实现】
1 #pragma once 2 #include3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 10 class calEquation 11 { 12 public: 13 int cal(const string str)//计算 14 { 15 if (str.length() == 0) 16 return 0; 17 return calFunc(str, 0)[0]; 18 } 19 20 private: 21 vector calFunc(const string str, int index) 22 { 23 stack data; 24 int num = 0; 25 vector v; 26 while (index < str.length() && str[index] != ')') 27 { 28 if (str[index] >= '0'&&str[index] <= '9') 29 num = num * 10 + str[index++] - '0'; 30 else if (str[index] != '(') 31 { 32 addNum(data, num); 33 string sybol = ""; 34 sybol = str[index++]; 35 data.push(sybol);//是运算符，加上 36 num = 0; 37 } 38 else//是左括号 39 { 40 v = calFunc(str, index + 1); 41 num = v[0]; 42 index = v[1] + 1; 43 } 44 } 45 addNum(data, num); 46 return { getNum(data), index }; 47 } 48 49 void addNum(stack &data, int num) 50 { 51 if (!data.empty()) 52 { 53 if (data.top() == "*" || data.top() == "/") 54 { 55 string add = data.top(); 56 data.pop(); 57 int b = stringToNum(data.top()); 58 data.pop(); 59 num = add == "*" ? b * num : b / num; 60 } 61 } 62 data.push(numToStr(num)); 63 } 64 65 66 int getNum(stack &data) 67 { 68 int sum = 0; 69 bool flag = true; 70 while (!data.empty()) 71 { 72 string str = data.top(); 73 data.pop(); 74 if (str == "+") 75 flag = true; 76 else if (str == "-") 77 flag = false; 78 else 79 sum += flag ? stringToNum(str) : -stringToNum(str); 80 } 81 return sum; 82 } 83 84 int stringToNum(string str)//字符转数字 85 { 86 int num; 87 stringstream ss; 88 ss << str; 89 ss >> num; 90 return num; 91 } 92 93 string numToStr(int num)//数字转字符 94 { 95 string str; 96 stringstream ss; 97 ss << num; 98 ss >> str; 99 return str;100 }101 };102 103 104 void Test()105 {106 string str;107 calEquation* p = new calEquation;108 str = "3+4";109 cout << str << "= " << p->cal(str) << endl;110 111 str = "3+4*5+2";112 cout << str << "= " << p->cal(str) << endl;113 114 str = "3+2+3*(1+3)";115 cout << str << "= " << p->cal(str) << endl;116 }