1、叠箱子问题
#include <iostream> #include <vector> #include <stack> using namespace std; int countNum(string input) { //用栈解决,0代表箱子左边缘'[' stack<int> stk; int length = input.length(); int i = 0; while (i < length) { char cur = input[i]; //左边缘入栈0 if (cur == '[') { stk.push(0); } //右边缘出栈中间的元素以及左边缘0 else if (cur == ']') { //栈内数字代表有多少个箱子,如果有多个数字就是相加 int count = 0; while (stk.top() != 0) { int temp = stk.top(); stk.pop(); count += temp; } //左边缘出栈 int left = stk.top(); stk.pop(); //外部的箱子也得算一个 count += 1; //将一对箱子内的总数入栈 stk.push(count); } //数字,代表有多个 else { int num = input[i] - '0'; //出栈 int bef = stk.top(); stk.pop(); //如果是左边界,直接把数字入栈,相当于数字乘1 if (bef == 0) stk.push(num); //如果是数字,代表内部有嵌套箱子,相乘后入栈 else stk.push(num * bef); } //前进一个字符 i++; } //完成后栈内可能有多个数字,对应 "[][][]"这种非嵌套类型 int num = 0; //弹栈计算总和 while (!stk.empty()) { num += stk.top(); stk.pop(); } return num; } int main() { string input; cin >> input; int result = countNum(input); cout << result << endl; return 0; }
全部评论
(1) 回帖