【題解】ZeroJudge f640: 函數運算式求值

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=f640
【解題想法】遞迴 或 堆疊

做法-1. 遞迴 Recursion

#include <iostream>
#include <string>
using namespace std;

int eval(){
    string s;
    cin >> s;
    if (s[0] == 'f') {
        int x = eval();
        return 2 * x - 3;
    } else if (s[0] == 'g') {
        int x = eval();
        int y = eval();
        return 2 * x + y - 7;
    } else if (s[0] == 'h') {
        int x = eval();
        int y = eval();
        int z = eval();
        return 3 * x - 2 * y + z;
    } else {
        return stoi(s);
    }
}

int main() {
    cout << eval() << endl;
    return 0;
}

做法-2. 堆疊 Stack

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

int main() {
    string s;
    stringstream ss;
    stack<string> stk1;
    stack<int> stk2;
    while (cin >> s) {
        stk1.push(s);
    }
    while (!stk1.empty()) {
        s = stk1.top();
        stk1.pop();
        if (s == "f") {
            int x = stk2.top(); stk2.pop();
            stk2.push(2 * x - 3);
        } else if (s == "g") {
            int x = stk2.top(); stk2.pop();
            int y = stk2.top(); stk2.pop();
            stk2.push(2 * x + y - 7);
        } else if (s == "h") {
            int x = stk2.top(); stk2.pop();
            int y = stk2.top(); stk2.pop();
            int z = stk2.top(); stk2.pop();
            stk2.push(3 * x - 2 * y + z);
        } else {
            stk2.push(stoi(s));
        }
    }
    cout << stk2.top() << endl;
    return 0;
}
分享本文 Share with friends