2023.1.19 PM 01:30 by CBJ
來源 : https://zerojudge.tw/ShowProblem?problemid=f640 出題者 : 2019年2月APCS 標籤 : 遞迴、stack 難易度 : 4
解題想法 : 此題最難的地方在於,想到該如何實作,筆者此處使用stack的解法。 對於一串合法的運算式,它的結尾必定會是數字,而對於每個英文字母(只會有f,g,h),其必定能夠獲得足夠的數字進行運算。 因此假如我們從尾端開始看起,只要遇到數字就推進stack,遇到f,g,h就從stack中pop出需要的數量,最後再將函數運算結果丟回stack中。 詳細可參考此文 : https://cbjsprogramdiary.com/2023/01/20/zerojudge-f640%e5%9c%96%e5%83%8f%e5%8c%96%e8%aa%aa%e6%98%8e/
#include<iostream>
#include<string> //string, stoi()
#include<vector> //vector
#include<algorithm> //reverse()
#include<stack> //stack
#include<cctype> //islower()
using namespace std;
int f(int x){ return 2*x-3; }
int g(int x,int y){ return 2*x+y-7; }
int h(int x,int y,int z){ return 3*x-2*y+z; }
int main(){
string s;
vector<string>v;
while(cin>>s) v.push_back(s);
reverse(v.begin(),v.end());
stack<int>st;
for(string now:v){
if(islower(now[0])){
int ans;
if(now=="f"){
int a=st.top(); st.pop();
st.push(f(a));
}
else if(now=="g"){
int a=st.top();st.pop();
int b=st.top();st.pop();
st.push(g(a,b));
}
else if(now=="h"){
int a=st.top(); st.pop();
int b=st.top(); st.pop();
int c=st.top(); st.pop();
st.push(h(a,b,c));
}
}
else st.push(stoi(now));
}
cout<<st.top()<<"\n";
return 0;
}

## Python language
def f(x): return 2*x-3
def g(x,y): return 2*x+y-7
def h(x,y,z): return 3*x-2*y+z
stk=[]
def stk_top(): return stk[-1]
def stk_push(x): stk.append(x)
def stk_pop(): return stk.pop()
v=reversed(input().split())
for now in v:
if now[0].islower():
if now=='f': stk_push(f(stk_pop()))
elif now=='g': stk_push(g(stk_pop(),stk_pop()))
elif now=='h': stk_push(h(stk_pop(),stk_pop(),stk_pop()))
else: stk_push(int(now))
print(stk_top())
