Chuyển biểu thức toán học sang RPN - LCOJ: Luyện Code Online Judge

STRPN - Chuyển biểu thức toán học sang RPN

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Bạn được cho một danh sách các biểu thức toán học đúng ở dạng trung tố chỉ chứa:

Biến: là các chữ cái latinh in thường a-z, (mỗi biến là một chữ cái)
Các toán tử hai ngôi: +, -,*, /, ^ (lũy thừa) với thứ tự ưu tiên như sau: +, - cùng độ ưu tiên thấp nhất; *, / cùng độ ưu tiên thứ hai, ^ có độ ưu tiên cao nhất
Các cặp dấu ngoặc

Hãy chuyển đổi biểu thức đó sang dạng hậu tố và giữ nguyên thứ tự các số hạng (RPN – ký pháp nghịch đảo Ba Lan)

Input

Dòng đầu chứa số nguyên dương ~T~ là số biểu thức;
~T~ dòng tiếp theo, mỗi dòng chứa một biểu thức dạng trung tố.

Giới hạn:

~1 ≤ T ≤ 100~; độ dài các biểu thức trung tố không quá ~400~.

Output

Ứng với mỗi biểu thức dạng trung tố, in ra biểu thức RPN tương ứng trên một dòng.

Sample

Input #1

3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output #1

abc*+
ab+zx+*
at+bac++cd+^*

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

include <bits/stdc++.h>

using namespace std;

// Hàm kiểm tra nếu c là toán tử bool is_op(char c) { return c=='+' || c=='-' || c=='*' || c=='/' || c=='^'; }

// Hàm ưu tiên toán tử int precedence(char op) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; if (op == '^') return 3; return 0; }

int main() { ios::syncwithstdio(false); cin.tie(nullptr);

string s;
// Đọc toàn bộ biểu thức (1 dòng)
getline(cin, s);

stack<char> st;
vector<string> output;

for (int i = 0; i < (int)s.size(); ) {
    if (isspace(s[i])) {
        ++i;
        continue;
    }
    // Nếu là số (có thể nhiều chữ số)
    if (isdigit(s[i])) {
        string num;
        while (i < (int)s.size() && isdigit(s[i])) {
            num.push_back(s[i]);
            ++i;
        }
        output.push_back(num);
    }
    else if (s[i] == '(') {
        st.push(s[i]);
        ++i;
    }
    else if (s[i] == ')') {
        while (!st.empty() && st.top() != '(') {
            output.push_back(string(1, st.top()));
            st.pop();
        }
        if (!st.empty() && st.top() == '(') st.pop();
        ++i;
    }
    else if (is_op(s[i])) {
        char op = s[i];
        // Xử lý ưu tiên, với ^ thường phải đặc biệt (right‑associative)
        while (!st.empty() && is_op(st.top()) &&
               ( (precedence(st.top()) > precedence(op)) ||
                 (precedence(st.top()) == precedence(op) && op != '^') )
               ) {
            output.push_back(string(1, st.top()));
            st.pop();
        }
        st.push(op);
        ++i;
    }
    else {
        // nếu có ký tự khác (ví dụ biến, chữ cái), bạn có thể thêm logic tương ứng
        // tạm: coi như bỏ qua
        ++i;
    }
}

// Đổ hết toán tử còn lại
while (!st.empty()) {
    if (is_op(st.top()))
        output.push_back(string(1, st.top()));
    st.pop();
}

// In output — tokens cách nhau bằng khoảng trắng
bool first = true;
for (auto &tok : output) {
    if (!first) cout << ' ';
    first = false;
    cout << tok;
}
cout << '\n';

return 0;

}

Lời giải cho bạn nào chưa biêt cách giải quyết như thế nào nha!

#include <bits/stdc++.h>
  using namespace std;


int precedence(char c) {
    if(c == '+' || c == '-') return 1;
    if(c == '*' || c == '/') return 2;
    if(c == '^') return 3;
    return 0;
}

void RPN() {
    stack<char> st;
    string s;
    getline(cin, s);
    string out = "";

    for(int i = 0; i < s.length(); i++) {
        if(s[i] == ' ') continue;

        if(isalnum(s[i])) { 
            out += s[i];
        } 
        else if(s[i] == '(') {
            st.push(s[i]);
        } 
        else if(s[i] == ')') {
            while(!st.empty() && st.top() != '(') {
                out += st.top();
                st.pop();
            }
            if(!st.empty()) st.pop();
        } 
        else if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '^') {
            while(!st.empty() && st.top() != '(' && precedence(st.top()) >= precedence(s[i])) {
                out += st.top();
                st.pop();
            }
            st.push(s[i]);
        }
    }

    while(!st.empty()) {
        out += st.top();
        st.pop();
    }

    cout << out << "\n";
}

int main() {
    ios::syncwithstdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    cin.ignore();
    while(t--) {
        RPN();
    }
    return 0;
}