A25116. 表达式求值
填空题
容易
知识点
题目描述
表达式求值
题目描述：
给定一个仅包含数字 1 到 9 的字符串 S，请在 S 中分别插入 1 个加号（+）、2 个加号。
注：
1）加号不能出现在 S 中第一位数字的前面或者最后一位数字的后面；
2）两个加号的位置不能相邻。
插入加号后的字符串可以看做是一个加法表达式，请找出所有可能出现的表达式，并输出所有表达式结果的总和。
例 1：S = "1234"；分别在字符串 "1234" 中插入 1 个加号、2 个加号，插入加号的表达式如下：
1）当插入 1 个加号时，表达式有 1 + 234、12 + 34、123 + 4，计算结果依次为 235、46、127；
2）当插入 2 个加号时，表达式有 1 + 2 + 34、1 + 23 + 4、12 + 3 + 4，计算结果依次为 37、28、19；
这些结果的总和为 492（235 + 46 + 127 + 37 + 28 + 19）。
例 2：S = "111"，分别在字符串 "111" 中插入 1 个加号、2 个加号，插入加号的表达式如下：
1）当插入 1 个加号时，表达式有 1 + 11，11 + 1，计算结果依次为 12、12；
2）当插入 2 个加号时，表达式有 1 + 1 + 1，计算结果为 3；
这些结果的总和为 27（12 + 12 + 3）。
输入描述：
输入一个仅包含数字 1 到 9 的字符串 S（3≤S的长度≤15）。
输出描述：
输出一个整数，表示所有可能出现的表达式的结果的总和。
样例输入：
1234样例输出：
492参考答案
#include <iostream>
#include <string>
#include <vector>
#include <cctype>
using namespace std;
// 将子串转为整数
int toInt(string s, int start, int end) {
int num = 0;
for (int i = start; i <= end; i++) {
num = num * 10 + (s[i] - '0');
}
return num;
}
int main() {
string s;
cin >> s;
int n = s.size();
long long totalSum = 0;
// 插入1个加号的情况
for (int i = 1; i <= n - 1; i++) {
int a = toInt(s, 0, i - 1);
int b = toInt(s, i, n - 1);
totalSum += (a + b);
}
// 插入2个加号的情况
for (int i = 1; i <= n - 2; i++) {
for (int j = i + 1; j <= n - 1; j++) {
int a = toInt(s, 0, i - 1);
int b = toInt(s, i, j - 1);
int c = toInt(s, j, n - 1);
totalSum += (a + b + c);
}
}
cout << totalSum << endl;
return 0;
}答案解析
枚举所有加号插入位置：
一个加号：在位置i插入，将字符串分为两部分求和。
两个加号：在位置i和j插入（i < j），分为三部分求和。
上一题
下一题