괄호가 없는 산술 표현식이 있다고 가정합니다. 우리의 임무는 그 표현의 가능한 모든 결과를 찾는 것입니다. 표현식이 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에 대해 다음을 수행하십시오. -
-
x의 왼쪽에 있는 모든 가능한 값을 재귀적으로 평가하고 값 목록을 L
로 둡니다. -
x의 오른쪽에 있는 모든 가능한 값을 재귀적으로 평가하고 값 목록을 R
로 둡니다. -
L:
의 모든 값을 반복합니다.-
R-
의 모든 값을 반복합니다.-
L 및 R의 현재 요소에 현재 연산자 x를 적용하고 평가된 값을 res
에 추가합니다.
-
-
-
- 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