ZeroJudge 解題筆記：m907. 方程式 (Equation)

作者：王一哲
日期：2025年6月5日


ZeroJudge 題目連結：m907. 方程式 (Equation)

解題想法

我將這題分成 3 個部分：中序轉後序、由後序運算式求值、解方程式，分別寫一個對應的函式，在主程式中呼叫這 3 個函式解題。

Python 程式碼

使用時間約為 21 ms，記憶體約為 3.4 MB，通過測試。

import sys

def infix_to_postfix(tokens):  # 中序轉後序
    st = []  # 暫存運算子用的堆疊
    postfix = []  # 儲存後序運算式的串列
    precedence = {'(': 0, '+':1, '*': 2}  # 運算子優先順序
    for token in tokens:  # 由 tokens 依序讀取 token
        if token.isnumeric() or token == 'x':  # 如果 token 是數字或 k
            postfix.append(token)  # 直接加入 postfix
        elif token == '(':  # 如果 token 是 (
            st.append(token)  # 先加入 st
        elif token == ')':  # 如果 token 是 )
            while st and st[-1] != '(':  # 如果 st 還有資料而且最後一項是 (
                postfix.append(st.pop())  # 移除 st 最後一項並加入 postfix
            st.pop()  # 移除 st 最後一項的 (
        elif token in precedence:  # 如果 token 在 precedence 之中
            while st and st[-1] != '(' and precedence[token] <= precedence[st[-1]]:  # 如果 token 的優先順序小於等於 st 的最後一項
                postfix.append(st.pop())  # 移除 st 最後一項並加入 postfix
            st.append(token)  # token 加入 st
    while st:  # 清空 st，加到 postfix
        postfix.append(st.pop())
    return postfix  # 回傳 postfix

def myevaluate(postfix):  # 由後序運算式求值，於 ZeroJudge 名稱不能用 evaluate_postfix 或 evaluate
    st = []  # 暫存用的堆疊，內容為 (x 項係數, 常數項)
    for token in postfix:  # 由 postfix 依序讀取 token
        if token.isnumeric():  # 如果 token 是數字
            st.append((0, int(token)))  # token 轉成整數再加入 st
        elif token == 'x':  # 如果 token 是 x
            st.append((1, 0))  # x 項係數 1 加入 st
        elif token == '+':  # 如果 token 是 +
            x1, c1 = st.pop()  # 取出 st 最後兩項，相加後再加入 st
            x2, c2 = st.pop()
            st.append((x1+x2, c1+c2))
        elif token == '*':  # 如果 token 是 *
            x1, c1 = st.pop()  # 取出 st 最後兩項，相乘後再加入 st
            x2, c2 = st.pop()
            st.append((x1*c2 + x2*c1, c1*c2))  # 題目保證沒有 x 平方項
    return st[-1][0], st[-1][1]  # 回傳 st 最後一項

def solve_equation(left_side, right_side):  # 解方程式，代入左、右側式子
    left_x, left_c = myevaluate(infix_to_postfix(left_side.split()))
    right_x, right_c = myevaluate(infix_to_postfix(right_side.split()))
    return (right_c - left_c) // (left_x - right_x)

for line in sys.stdin:
    left_side = line.strip()  # 左側式子
    right_side = input().strip()  # 右側式子
    print(solve_equation(left_side, right_side))

C++ 程式碼

使用時間約為 3 ms，記憶體約為 384 kB，通過測試。

#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <sstream>
#include <map>
#include <cctype>  // for isdigit
using namespace std;

bool isnumeric(string s) {  // 字串 s 是否為數字
    for(char c : s) {  // 由 s 依序讀取字元 c
        if (!isdigit(c)) return false;  // 如果 c 不是數字 0 ~ 9，回傳 false
    }
    return true;  // s 是數字，回傳 true
}

void infix_to_postfix(vector<string>& tokens, vector<string>& postfix) {
    vector<string> st;  // 暫存運算子用的堆疊
    map<string, int> precedence = {{"(", 0}, {"+", 1}, {"*", 2}};  // 運算子優先順序
    for(auto token : tokens) {  // 由 tokens 依序讀取 token
        if (isnumeric(token) || token == "x") {  // 如果 token 是數字或 x
            postfix.push_back(token);  // 直接存入 postfix
        } else if (token == "(") {  // 如果 token 是 (
            st.push_back(token);  // 先存入 st
        } else if (token == ")") {  // 如果 token 是 )
            while(!st.empty() && st.back() != "(") {  // 如果 st 有資料而且最後一項不是 (
                postfix.push_back(st.back());  // st 最後一項加入 postfix
                st.pop_back();  // 移除 st 最後一項
            }
            st.pop_back();  // 移除 st 最後一項的 (
        } else if (precedence.count(token) == 1) {  // 如果 token 在 precedence 之中
            if (!st.empty() && st.back() != "(" && precedence[token] <= precedence[st.back()]) {
                postfix.push_back(st.back());  // st 最後一項加入 postfix
                st.pop_back();  // 移除 st 最後一項
            }
            st.push_back(token);  // token 加入 st
        }
    }
    while(!st.empty()) {  // 清空 st，加到 postfix
        postfix.push_back(st.back());
        st.pop_back();
    }
}

pair<int, int> myevaluate(vector<string>& postfix) {  // 由後序運算式求值
    vector<pair<int, int>> st;  // 暫存運算結果的堆疊，資料為 (x 項係數, 常數項)
    for(auto token : postfix) {  // 從 postfix 依序讀取 token
        if (isnumeric(token)) {  // 如果 token 是整數
            st.push_back(make_pair(0, stoi(token)));
        } else if (token == "x") {  // 如果 token 是 x
            st.push_back(make_pair(1, 0));
        } else if (token == "+") {  // 如果 token 是 +
            int x1 = st.back().first, c1 = st.back().second;
            st.pop_back();
            int x2 = st.back().first, c2 = st.back().second;
            st.pop_back();
            st.push_back(make_pair(x1+x2, c1+c2));
        } else if (token == "*") {  // 如果 token 是 *
            int x1 = st.back().first, c1 = st.back().second;
            st.pop_back();
            int x2 = st.back().first, c2 = st.back().second;
            st.pop_back();
            st.push_back(make_pair(x1*c2 + x2*c1, c1*c2));
        }
    }
    return st.back();
}

int solve_equation(vector<string>& left_post, vector<string>& right_post) {
    pair<int, int> left = myevaluate(left_post);
    pair<int, int> right = myevaluate(right_post);
    int left_x = left.first, left_c = left.second, right_x = right.first, right_c = right.second;
    return (right_c - left_c) / (left_x - right_x);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;  // 暫存算式用的字串
    stringstream ss;  // 暫存算式用的 sstream 物件
    while(getline(cin, s)) {
        vector<string> left_tokens, right_tokens;  // 左、右兩側中序運算式
        ss.clear(); ss << s;  // 先清空 ss，再將 s 存入 ss
        while(ss >> s) left_tokens.push_back(s);  // 從 ss 讀取資料存入 left_tokens
        getline(cin, s);  // 讀取一行字串
        ss.clear(); ss << s;  // 先清空 ss，再將 s 存入 ss
        while(ss >> s) right_tokens.push_back(s);  // 從 ss 讀取資料存入 right_tokens
        vector<string> left_post, right_post;  // 左、右兩側後序運算式
        infix_to_postfix(left_tokens, left_post);  // 轉成後序運算式
        infix_to_postfix(right_tokens, right_post);  // 轉成後序運算式
        cout << solve_equation(left_post, right_post) << "\n";
    }
    return 0;
}