พิมพ์นิพจน์ที่เป็นไปได้ทั้งหมดที่ประเมินเป็นเป้าหมายใน C++

ในปัญหานี้ เราได้รับสตริงของจำนวนเต็มตั้งแต่ 0 ถึง 9 และค่าเป้าหมาย เราต้องพิมพ์วิธีที่เราสามารถสร้างนิพจน์โดยใช้การดำเนินการ +, - และ * ซึ่งประเมินค่าเท่ากับเป้าหมาย

มาดูตัวอย่างเพื่อทำความเข้าใจหัวข้อกันดีกว่า −

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