ZeroJudge 解題筆記：f377. 運算式轉換

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


ZeroJudge 題目連結：f377. 運算式轉換

解題想法

用堆疊處理算式，同時要注意括號配對的狀況。

Python 程式碼

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

import sys

for line in sys.stdin:
    tmp = []                                 # 暫存運算子及變數的串列
    ans = []                                 # 儲存答案的串列
    for d in line.split():                   # 依序從串列 data 取出字元並儲存到變數 d
        if d == ")":                         # 若 d 為 )
            while tmp[-1] != "(":            # 當 tmp 最後一項不是 ( 繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.pop()                        # 結束 while 迴圈後移除 tmp 最後一項，此時為 (
        elif d == "(":                       # 若 d 為 )
            tmp.append(d)                    # 將 d 加到 tmp 最後面
        elif d in "*/":                      # 若 d 為 */
            while tmp and tmp[-1] in "*/":   # 當 tmp 之中有資料且最後一項為 */ 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        elif d in "+-":                      # 若 d 為 ＋＝
            while tmp and tmp[-1] in "+-*/": # 當 tmp 之中有資料且最後一項為 +-*/ 時繼續執行
                ans.append(tmp.pop())        # 將 tmp 最後一項移出並加到 ans 最後面
            tmp.append(d)                    # 結束 while 迴圈後將 d 加到 tmp 最後面
        else:                                # 若 d 不為 ()+-*/ 即為變數
            ans.append(d)                    # 直接加到 ans 最後面 
    # 移除 tmp 最後一項並加到 ans 最後面，直到 tmp 無資料時停止
    while tmp: ans.append(tmp.pop())
    print(*ans)

C++ 程式碼

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

#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    string d;                 // 暫存讀取資料用的字串 d
    stringstream ss;          // 暫存資料流用的 ss
    while(getline(cin, d)) {  // 由 cin 讀取整行資料存進字串 d
        ss.clear();           // 清理 ss，如果有測資中有多行資料一定要執行
        ss << d;              // 將字串 d 的資料傳給 ss
        stack<string> tmp;    // 暫存運算子及變數的 tmp
        vector<string> ans;   // 儲存答案的 ans
        while(ss >> d) {      // 依序從串列 ss 取出字元並儲存到變數 s
            if (d == ")") {                   // 若 d 為 )
                while(tmp.top() != "(") {     // 當 tmp 最後一項不是 ( 繼續執行
                    ans.push_back(tmp.top()); // 將 tmp 最後一項加到 ans 最後面
                    tmp.pop();                // 除除 tmp 最後一項
                }
                tmp.pop();                    // 結束 while 迴圈後移除 tmp 最後一項，此時為 (
            } else if (d == "(") {            // 若 d 為 )
                tmp.push(d);                  // 將 d 加到 tmp 最後面
            } else if (d == "*" || d == "/") {  // 若 d 為 */
                while(!tmp.empty() && (tmp.top() == "*" || tmp.top() == "/")) {   // 當 tmp 之中有資料且最後一項為 */ 時繼續執行
                    ans.push_back(tmp.top()); // 將 tmp 最後一項加到 ans 最後面
                    tmp.pop();                // 除除 tmp 最後一項
                }
                tmp.push(d);                  // 結束 while 迴圈後將 d 加到 tmp 最後面
            } else if (d == "+" || d == "-") {  // 若 d 為 ＋＝
                while(!tmp.empty() && (tmp.top() == "+" || tmp.top() == "-" || tmp.top() == "*" || tmp.top() == "/")) {  // 當 tmp 之中有資料且最後一項為 +-*/ 時繼續執行
                    ans.push_back(tmp.top()); // tmp 最後一項移出並加到 ans 最後面
                    tmp.pop();                // 除除 tmp 最後一項
                }
                tmp.push(d);                  // 結束 while 迴圈後將 d 加到 tmp 最後面
            } else {                          // 若 d 不為 ()+-*/ 即為變數
                ans.push_back(d);             // 直接加到 ans 最後面 
            }
        }
        // 移除 tmp 最後一項並加到 ans 最後面，直到 tmp 無資料時停止
        while(!tmp.empty()) {
            ans.push_back(tmp.top());
            tmp.pop();
        }
        // 依照題目規定的格式輸出 ans
        for(int i=0; i<(int)ans.size(); i++) {
            cout << ans[i] << " \n"[i == (int)ans.size()-1];
        }
    }
    return 0;
}