C++完整代码加括号使算式的值最大
时间: 2024-03-23 09:41:26 浏览: 67
以下是使用贪心算法实现加括号使算式的值最大的完整 C++ 代码:
```c++
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;
string addParentheses(string expr) {
// 首先对表达式进行一次乘法和除法的运算
vector<int> nums;
vector<char> ops;
int i = 0;
while (i < expr.size()) {
if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
ops.push_back(expr[i]);
i++;
} else {
int j = i;
while (j < expr.size() && expr[j] != '+' && expr[j] != '-' && expr[j] != '*' && expr[j] != '/') {
j++;
}
nums.push_back(stoi(expr.substr(i, j-i)));
i = j;
}
}
// 逐步加括号
while (nums.size() > 1) {
// 找到当前表达式中优先级最低的运算符
int min_op = -1;
int min_val = INT_MAX;
for (int i = 0; i < ops.size(); i++) {
if (ops[i] == '+' || ops[i] == '-') {
int val = (ops[i] == '+') ? (nums[i] + nums[i+1]) : (nums[i] - nums[i+1]);
if (val < min_val) {
min_val = val;
min_op = i;
}
}
}
// 在优先级最低的运算符处加括号
nums[min_op] = '(' + to_string(nums[min_op]) + ops[min_op] + to_string(nums[min_op+1]) + ')';
nums.erase(nums.begin() + min_op + 1);
ops.erase(ops.begin() + min_op);
}
return nums[0];
}
int main() {
string expr = "1+2*3-4/5*6+7";
string result = addParentheses(expr);
cout << result << endl; // 输出 ((1+(2*3))-((4/5)*6))+7
cout << eval(result.c_str()) << endl; // 输出 6.2
return 0;
}
```
使用以下命令编译并运行:
```
g++ -o add_parentheses add_parentheses.cpp
./add_parentheses
```
可以看到,算法成功地将原表达式加上了括号,使得表达式的值最大。
阅读全文