Bài toán tìm biểu thức toán học

[urek-mazino (Đỗ Đăng Khôi)]

Đề bài :
Cho chuỗi "((((1?2)?3)?4)?5)?6 = 36"
Thay thế dấu chấm hỏi ? bằng các toán tử '+', '-', '*', '/'
Sao cho biểu thức đúng
Output :

((((1*2)*3)/4)+5)*6
((((1*2)+3)/4)+5)*6
((((1*2)+3)-4)+5)*6
((((1/2)-3)+4)+5)*6
((((1+2)+3)/4)+5)*6
((((1-2)*3)+4)+5)*6
((((1-2)+3)+4)*5)+6

Em giải theo cách :

• Liệt kêu các trường hợp của biểu thức bằng giải thuật sinh chỉnh hợp lặp hiện thực theo giải thuật quay lui BackTracking (Hàm Try)
• Chuyển biểu thức dạng trung tố sang hậu tố (Hàm I2P)
• Tính toán biểu thức theo giải thuật người Ba lan (Hàm CalculateRPN)

Em gặp bài này vì có 1 người bạn hỏi. Không biết các bác có hướng nào làm khác cho bài toán này không.

#include <iostream>
#include <cstdint>
#include <string>
#include <stack>
#define SIZE 5 // Số dấu ?
using namespace std;
// # Khai báo prototype
int rnk(char ch);         // Hàm tính độ ưu tiên toán tử
string I2P(string s);     // Hàm chuyển biểu thức trung tố sang hậu tố
int CaculateRPN(string s);// Hàm tính toán theo giải thuật người ba lan

// Dữ liệu kiểm tra
string Ex = "((((1?2)?3)?4)?5)?6";
string Rs = "36";
// Mảng chứa các toán tử
string Op = "*/+-";
// Mảng chứa các cấu hình sinh chỉnh hợp lặp
char Se[SIZE];


// Hàm in cấu hình
void Find() {
    // Tạo biểu thức trung tố
    string IE(Ex); uint8_t index = 0;
    for(int i = 0; i < IE.length(); ++i) 
        if(Ex[i] == '?') IE[i] = Se[index++];
    // Chuyển biểu thức trung tố -> hậu tố
    string PE = I2P(IE);
    // Tính toán theo giải thuật người Ba lan
    if(CaculateRPN(PE) == stoi(Rs)) cout << IE << endl;
}
// Giải thuật BackTracking
// Sinh chỉnh hợp lặp
void Try(int i) {
    for(int j = 0; j < 4; ++j) {
        Se[i] = Op[j];
        if(i == SIZE - 1) Find();
        else Try(i + 1);
    }
}
// Kiểm tra hàm
int main()
{
    Try(0);
    return 0;
}

int rnk(char ch) {
    switch(ch) {
        case '*' : case '/' : return 2;
        case '+' : case '-' : return 1;
    }
    return 0;
}

string I2P(string s) {
    string result = "";
    stack<char> stk;
    for(auto ch : s) switch(ch) {
        case '(' : stk.push(ch); break;

        case ')' :
            char temp;
            do {
                temp = stk.top(); stk.pop();
                if(temp != '(') result += temp;
            } while(temp != '('); break;

        case '+' : case '-' :
        case '*' : case '/' :
            while(!stk.empty() && rnk(ch) <= rnk(stk.top()))
                {result += stk.top(); stk.pop();}
            stk.push(ch); break;
        
        default : result += ch; break;
    }
    while(!stk.empty()) 
        {result += stk.top();stk.pop();}
    return result;
}

int CaculateRPN(string s) {
    stack<int> stk;
    int a, b;
    for(char ch : s) switch(ch) {
        case '+' :
            b = stk.top(); stk.pop();
            a = stk.top(); stk.pop();
            stk.push(a + b); break;
        case '-' :
            b = stk.top(); stk.pop();
            a = stk.top(); stk.pop();
            stk.push(a - b); break;
        case '*' :
            b = stk.top(); stk.pop();
            a = stk.top(); stk.pop();
            stk.push(a * b); break;
        case '/' :
            b = stk.top(); stk.pop();
            a = stk.top(); stk.pop();
            stk.push(a / b); break;
        default : 
            string str = "";
            str += ch;
            stk.push(stoi(str));
            break;
    }
    return stk.top();
}

[Phong_Ky_Vo (Tao Không Ngu.)]

Hi Đỗ Đăng Khôi.
Theo mình có 2 :

1. Chia làm 2 bước là sinh tổ hợp và tính toán tổ hợp (Như cách của bạn):
   Ưu điểm : Đơn giản, dễ hiểu, code thành từng bước rõ ràng, dễ mở rộng và phân module.
   Nhược điểm : Hiệu năng không cao do phải thực hiện lặp lại bước chuyển về hậu tố nhiều lần.
2. Thực hiện chuyển hậu tố 1 lần sau đó thay giá trị phép toán trên sâu hậu tố (Với +, - như nhau)
   Ưu điểm : hiệu năng cao hơn.
   Nhược điểm code phức tạp, v.v.v…

P/S Theo mình thì bạn có thể thử cách 2 hoặc dùng cây để cài đoạt hàm tính biểu thức.

[tntxtnt]

cái ngoặc đơn kia là để đơn giản hóa bài toán mà, 1?2 lúc nào cũng được tính trước, ra kết quả a rồi tính a?3 ra b, rồi tính b?4 ra c, rồi tính c?5 ra d, rồi tính d?6 ra kết quả :V Chạy biến i từ 0 tới 4⁵ là xong rồi :V

[tntxtnt]

code ngắn :V

#include <cstdio>
#include <string>

std::string getOps(int k)
{
    std::string ret(5, ' ');
    for (int i = 0; i < 5; ++i, k /= 4) ret[i] = "+-*/"[k % 4];
    return ret;
}

int eval(const std::string& ops)
{
    int a = 1, b = 2;
    for (char c : ops) switch (c)
        {
        case '+': a += b++; break;
        case '-': a -= b++; break;
        case '*': a *= b++; break;
        default: a /= b++; break;
        }
    return a;
}

int main()
{
    for (int i = 1024; i--;)
    {
        auto ops = getOps(i);
        auto res = eval(ops);
        if (res == 36)
            printf("((((1%c2)%c3)%c4)%c5)%c6 = %d\n", ops[0], ops[1], ops[2],
                   ops[3], ops[4], res);
    }
}

edit: ngắn tí nữa :V