C++에서 대상으로 평가되는 가능한 모든 표현식 인쇄

이 문제에서는 0에서 9까지의 정수 문자열과 목표 값이 제공됩니다. target과 같은 값으로 평가되는 +, -, * 연산을 사용하여 표현식을 생성할 수 있는 방법을 출력해야 합니다.

주제를 더 잘 이해하기 위해 예를 들어 보겠습니다 -

Input: string = “123” , target= 6
Output: { “1+2+3”, “1*2*3” }

이 문제를 해결하기 위해 가능한 모든 이항 연산자를 숫자 사이에 놓고 표현식의 결과를 대상 값으로 확인하여 표현식을 만듭니다.

결과 표현을 평가할 재귀 메서드에 모든 값을 전달합니다. 숫자가 0에서 시작하면 무시합니다.

예시

#include <bits/stdc++.h>
using namespace std;
void generateExpressionForTarget(vector<string>& res, string curExp,
string input, int target, int pos,int curVal, int last){
   if (pos == input.length()){
      if (curVal == target)
         res.push_back(curExp);
      return;
   }
   for (int i = pos; i < input.length(); i++){
      if (i != pos && input[pos] == '0')
         break;
      string part = input.substr(pos, i + 1 - pos);
      int cur = atoi(part.c_str());
      if (pos == 0)
         generateExpressionForTarget(res, curExp + part, input, target, i + 1, cur, cur);
      else{
         generateExpressionForTarget(res, curExp + "+" + part, input, target, i + 1, curVal + cur, cur);
         generateExpressionForTarget(res, curExp + "-" + part, input, target, i + 1, curVal - cur, -cur);
         generateExpressionForTarget(res, curExp + "*" + part, input, target, i + 1, curVal - last + last * cur, last * cur);
      }
   }
}
vector<string>generateExpression(string input, int target){
   vector<string> res;
   generateExpressionForTarget(res, "", input, target, 0, 0, 0);
   return res;
}
int main(){
   string input = "345";
   int target = 12;
   cout<<"The expressions are: \n";
   vector<string> res = generateExpression(input, target);
   for (int i = 0; i < res.size(); i++)
   cout << res[i] << " ";
   cout << endl;
   return 0;
}

출력

표현식은 -

3+4+5