2019/2 函數運算式求值

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())

相關文章

分享此文：