f698 - 後序運算式求值
題目描述
題目要求實作一個後序運算式 (Reverse Polish Notation, RPN) 的求值器。輸入是一個包含整數和運算子的字串，運算子包括加 (+)、減 (-)、乘 (*)、除 (/)。運算子和運算元之間用空格分隔。
解題思路
使用堆疊 (Stack) 來解決這個問題。遍歷輸入字串，如果遇到數字，就將其轉換為整數並壓入堆疊。如果遇到運算子，則從堆疊中彈出兩個運算元，執行運算，然後將結果壓回堆疊。最終，堆疊中只剩一個值，這個值就是整個運算式的結果。
複雜度分析
- 時間複雜度: O(n)，其中 n 是輸入字串的長度。因為需要遍歷整個字串一次。
- 空間複雜度: O(n)，在最壞的情況下，如果輸入字串只包含數字，則堆疊需要儲存所有數字。
程式碼
#include <iostream>
#include <stack>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string input;
getline(cin,input);
input+=' ';
stack <long long int> num;
int il=input.length();
for(int i=0;i<il;++i){
if(input[i]=='+'){
long long int tmp=num.top();
num.pop();
num.top()+=tmp;
}
else if(input[i]=='-'&&input[i+1]==' '){
long long int tmp=num.top();
num.pop();
num.top()-=tmp;
}
else if(input[i]=='*'){
long long int tmp=num.top();
num.pop();
num.top()*=tmp;
}
else if(input[i]=='/'){
long long int tmp=num.top();
num.pop();
num.top()/=tmp;
}
else if(input[i]>='0'||input[i]=='-'){
long long int t=1;
if(input[i]=='-'){
t=-1;
++i;
}
long long int ntmp=0;
while(input[i]>='0'&&input[i]<='9'){
ntmp*=10;
ntmp+=input[i++]-'0';
}
num.push(ntmp*t);
}
}
cout << num.top();
}