f640 - 函數運算式求值
題目描述
題目給定三個函數 f(x) = 2x - 3, g(x, y) = 2x + y - 7, h(x, y, z) = 3x - 2y + z，以及一個函數運算式，運算式由這些函數和整數參數組成，參數間以空格分隔。要求計算並輸出運算式的值。運算式可以嵌套，例如 h f 5 g 3 4 3 代表 h(f(5), g(3, 4), 3)。
解題思路
這題的核心是將輸入的字串解析，並根據函數名稱和參數進行計算。由於輸入的運算式是後綴表達式（Postfix notation），因此可以使用堆疊（Stack）來進行求值。
- 字串解析： 從字串的末尾開始，逐個字符地讀取。
- 數字處理： 如果讀取的字符是數字，則將其轉換為整數，並將其壓入堆疊中。
- 函數處理： 如果讀取的字符是函數名稱（f, g, h），則從堆疊中彈出所需的參數數量，根據函數的定義進行計算，然後將結果壓入堆疊中。
- 最終結果： 讀取完整個字串後，堆疊中只剩一個值，這個值就是運算式的結果。
複雜度分析
- 時間複雜度: O(n)，其中 n 是輸入字串的長度。因為需要遍歷整個字串一次。
- 空間複雜度: O(n)，在最壞的情況下，堆疊可能需要存儲所有輸入的參數。
程式碼
#include <iostream>
#include <stack>
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;
}
stack <int> sk;
int ans=0;
int main(){
string a;
getline(cin,a);
int al=a.length();
for(int i=al-1;i>=0;--i){
if(a[i]=='f'){
int tmp=f(sk.top());
sk.pop();
sk.push(tmp);
}
else if(a[i]=='g'){
int tmp=sk.top();
sk.pop();
int tmp2=sk.top();
sk.pop();
sk.push(g(tmp,tmp2));
}
else if(a[i]=='h'){
int tmp=sk.top();
sk.pop();
int tmp2=sk.top();
sk.pop();
int tmp3=sk.top();
sk.pop();
sk.push(h(tmp,tmp2,tmp3));
}
else if(a[i]>='0'&&a[i]<='9'){
int tmp=0,v=1;
while(a[i]>='0'&&a[i]<='9'){
tmp+=(a[i]-'0')*v;
v*=10;
--i;
}
if(a[i]=='-')tmp*=-1;
sk.push(tmp);
}
}
cout << sk.top();
}