2 条题解
-
0
#include <bits/stdc++.h> #define ll long long #define endl '\n' using namespace std; const int N = 1e5 + 5; string s; int nums(int l, int r) { int cnt = 0; for (int i = l; i <= r; i++) cnt = cnt * 10 + (s[i] - '0'); return cnt; } int calc(int l, int r) { if (l > r) return 0; int pos1 = -1, pos2 = -1, pos3 = -1; // ops1 : +- ; pos2 : */ ; pos3 : ^ int cnt = 0; // 标记左右括号 for (int i = l; i <= r; i++) { // 统计当前范围内的括号个数 if (s[i] == '(') cnt++; if (s[i] == ')') cnt--; // 定位这个范围内相应运算符号最后一次出现的地点(越早被定位,递归深度越浅,越晚被执行运算) // 这里是从递归角度出发确定相同优先级的运算符的执行顺序 if ((s[i] == '+' || s[i] == '-') && cnt == 0) pos1 = i; if ((s[i] == '*' || s[i] == '/') && cnt == 0) pos2 = i; if (s[i] == '^' && cnt == 0) pos3 = i; } // 在当前范围内没有符号的情况下,进行条件判断 if (pos1 == -1 && pos2 == -1 && pos3 == -1) { //// 多余括号情况 // 左括号多余 if (cnt > 0 && s[l] == '(') return calc(l+1, r); // 右括号多余 else if (cnt < 0 && s[r] == ')') return calc(l, r-1); //// cnt == 0, 说明要么是数字,要么有一对括号括住它 else if (cnt == 0 && s[l] == '(' && s[r] == ')') return calc(l+1, r-1); else return nums(l, r); } // 按优先级递归 if (pos1 != -1) { // + - 优先级最低 if (s[pos1] == '+') return calc(l, pos1-1) + calc(pos1+1, r); if (s[pos1] == '-') return calc(l, pos1-1) - calc(pos1+1, r); } else if (pos2 != -1) { // * / 优先级中等 if (s[pos2] == '*') return calc(l, pos2-1) * calc(pos2+1, r); if (s[pos2] == '/') return calc(l, pos2-1) / calc(pos2+1, r); } else if (pos3 != -1) { // ^ 优先级最高 return (int)pow(calc(l, pos3-1), calc(pos3+1, r)); } return 0; } int main () { cin >> s; cout << calc(0, s.length()-1); return 0; }
信息
- ID
- 188
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 16
- 已通过
- 3
- 上传者