d016 - Error
題目描述
題目要求讀取包含數字和運算符的字串，並計算表達式的值。輸入為多行字串，每行字串包含一個算術表達式，表達式中只包含非負整數和 '+', '-', '*', '/', '%' 運算符。
解題思路
程式碼使用堆疊 (stack) 來儲存數字，並根據讀取的運算符執行相應的運算。程式逐字讀取輸入字串，如果遇到數字，則將其轉換為整數並推入堆疊。如果遇到運算符，則從堆疊中彈出一個或兩個數字，執行運算，然後將結果推回堆疊。最後，程式輸出堆疊頂部的結果。
複雜度分析
- 時間複雜度: O(N)，其中 N 是輸入字串的長度。因為程式需要遍歷整個輸入字串一次。
- 空間複雜度: O(N)，在最壞的情況下，如果輸入字串只包含數字，則堆疊可能需要儲存所有數字。
程式碼
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main(){
stack<int> s;
string a,b;
int x=0,i=0;
while(getline(cin,a)){
for(i=0,b.clear();i<a.length();i++){
while(a[i]<=57&&a[i]>=48){
b+=a[i];
i++;
}
x=0;
while(b.length()>0){
for(int i=0;i<b.length();i++){
x+=b[i]-48;
x*=10;
}
x/=10;
s.push(x);
b.clear();
}
x=0;
if(a[i]=='+'){
x=s.top();
s.pop();
s.top()+=x;
}
else if(a[i]=='-'){
x-=s.top();
s.pop();
s.top()+=x;
}
else if(a[i]=='*'){
x+=s.top();
s.pop();
s.top()*=x;
}
else if(a[i]=='/'){
x+=s.top();
s.pop();
s.top()/=x;
}
else if(a[i]=='%'){
x+=s.top();
s.pop();
s.top()%=x;
}
}
cout << s.top() << endl;
}
}