查找C ++中给定表达式的所有可能结果
假设我们有一个不带括号的算术表达式。我们的任务是找到该表达的所有可能结果。假设表达式像1+2*3-4,可以这样解释:
1+(2*(3-4))=1+(2*-1)=-1
(1+2)*(3-4)=3*-1=-3
1+(((2*3)-4)=1+(6-4)=3
((1+2)*3)-4=(3*3)-4=5
1+(2*3)-4=1+6–4=3
为了解决这个问题,我们必须遵循以下步骤-
最初将res设置为空
对于每个运算符x,请执行以下操作-
遍历R−中的所有值
将当前运算符x应用于L和R中的当前元素,并将评估值添加到res
递归计算x左边的所有可能值,让值列表为L
递归评估x右边的所有可能值,让值列表为R
循环遍历L中的所有值:
返回res作为输出
示例
#include<iostream> #include<vector> using namespace std; int solve(int a, char op, int b) { if (op=='+') return a+b; if (op=='-') return a-b; if (op == '*') return a*b; } vector<int> getAllResults(string expr, int low, int high) { vector<int> res; if (low == high) { res.push_back(expr[low] - '0'); return res; } if (low == (high-2)) { int num = solve(expr[low]-'0', expr[low+1], expr[low+2]-'0'); res.push_back(num); return res; } for (int i=low+1; i<=high; i+=2) { vector<int> L = evaluateAll(expr, low, i-1); vector R = evaluateAll(expr, i+1, high); for (int s1=0; s1<L.size(); s1++) { for (int s2=0; s2<R.size(); s2++) { int val = solve(L[s1], expr[i], R[s2]); res.push_back(val); } } } return res; } int main() { string expr = "1+2*3-4"; vector<int> ans = getAllResults(expr, 0, expr.length()-1); for (int i=0; i< ans.size(); i++) cout << ans[i] << endl; }
输出结果
2 1 4 3 5 6 7 8