【C++】stack和queue拓展學習

1.反向迭代器思路及實現

1.1. 源碼及框架分析

1.2. 實現反向迭代器

2.stack和queue練習拓展-計算器實現

2.1. 后綴表達式概念

2.2. 后綴表達式運算規則

2.3. 中綴表達式轉后綴表達式

2.3.1 轉換思路

2.3.2 代碼實現

2.4. 計算器實現

1.反向迭代器思路及實現

1.1. 源碼及框架分析

SGI-STL30版本源代碼，反向迭代器實現的核心源碼在stl_iterator.h中。

前文我們了解到了正向迭代器是基于原生指針的封裝實現，反向迭代器的邏輯與正向迭代器的邏輯正好相反，代碼應該高度相似，因此在學習了stack與queue之后，明白了適配器思想，我們就復用正向迭代器代碼實現反向迭代器，減少代碼冗余。

下面我們截出vector和list的的反向迭代器結構框架核心部分截取出來如下：

// stl_list.h
template <class T, class Alloc = alloc>
class list {
public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtypedef reverse_iterator<const_iterator> const_reverse_iterator;typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */typedef reverse_bidirectional_iterator<const_iterator, value_type,const_reference, difference_type> const_reverse_iterator;typedef reverse_bidirectional_iterator<iterator, value_type, reference,difference_type> reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */iterator begin() { return (link_type)((*node).next); }const_iterator begin() const { return (link_type)((*node).next); }iterator end() { return node; }const_iterator end() const { return node; }reverse_iterator rbegin() { return reverse_iterator(end()); }const_reverse_iterator rbegin() const {returnconst_reverse_iterator(end());}reverse_iterator rend() { return reverse_iterator(begin()); }const_reverse_iterator rend() const {returnconst_reverse_iterator(begin());}
};
// stl_vector.h
template <class T, class Alloc = alloc>
class vector {
public:typedef T value_type;typedef value_type* iterator;
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtypedef reverse_iterator<const_iterator> const_reverse_iterator;typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */typedef reverse_iterator<const_iterator, value_type, const_reference,difference_type> const_reverse_iterator;typedef reverse_iterator<iterator, value_type, reference, difference_type>reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */iterator begin() { return start; }const_iterator begin() const { return start; }iterator end() { return finish; }const_iterator end() const { return finish; }reverse_iterator rbegin() { return reverse_iterator(end()); }const_reverse_iterator rbegin() const {returnconst_reverse_iterator(end());}reverse_iterator rend() { return reverse_iterator(begin()); }const_reverse_iterator rend() const {returnconst_reverse_iterator(begin());}
};
// stl_iterator.h
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
// This is the new version of reverse_iterator, as defined in the
// draft C++ standard. It relies on the iterator_traits template,
// which in turn relies on partial specialization. The class
// reverse_bidirectional_iterator is no longer part of the draft
// standard, but it is retained for backward compatibility.
template <class Iterator>
class reverse_iterator
{
protected:Iterator current;
public:typedef typename iterator_traits<Iterator>::iterator_categoryiterator_category;typedef typename iterator_traits<Iterator>::value_typevalue_type;typedef typename iterator_traits<Iterator>::difference_typedifference_type;typedef typename iterator_traits<Iterator>::pointerpointer;typedef typename iterator_traits<Iterator>::referencereference;typedef Iterator iterator_type;typedef reverse_iterator<Iterator> self;
public:reverse_iterator() {}explicit reverse_iterator(iterator_type x) : current(x) {}reverse_iterator(const self& x) : current(x.current) {}
#ifdef __STL_MEMBER_TEMPLATEStemplate <class Iter>reverse_iterator(const reverse_iterator<Iter>& x) : current(x.current) {}
#endif /* __STL_MEMBER_TEMPLATES */iterator_type base() const { return current; }reference operator*() const {Iterator tmp = current;return *--tmp;}
#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */self& operator++() {--current;return *this;}self operator++(int) {self tmp = *this;--current;return tmp;}self& operator--() {++current;return *this;}self operator--(int) {self tmp = *this;++current;return tmp;}self operator+(difference_type n) const {return self(current - n);}self& operator+=(difference_type n) {current -= n;return *this;}self operator-(difference_type n) const {return self(current + n);}self& operator-=(difference_type n) {current += n;return *this;}reference operator[](difference_type n) const { return *(*this + n); }
};
template <class Iterator>
inline bool operator==(const reverse_iterator<Iterator>& x,const reverse_iterator<Iterator>& y) {return x.base() == y.base();
}
template <class Iterator>
inline bool operator<(const reverse_iterator<Iterator>& x,const reverse_iterator<Iterator>& y) {return y.base() < x.base();
}
template <class Iterator>
inline typename reverse_iterator<Iterator>::difference_type
operator-(const reverse_iterator<Iterator>& x,const reverse_iterator<Iterator>& y) {return y.base() - x.base();
}
template <class Iterator>
inline reverse_iterator<Iterator>
operator+(reverse_iterator<Iterator>::difference_type n,const reverse_iterator<Iterator>& x) {return reverse_iterator<Iterator>(x.base() - n);
}
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// This is the old version of reverse_iterator, as found in the original
// HP STL. It does not use partial specialization.
template <class BidirectionalIterator, class T, class Reference = T&,class Distance = ptrdiff_t>
class reverse_bidirectional_iterator {typedef reverse_bidirectional_iterator<BidirectionalIterator, T, Reference,Distance> self;
protected:BidirectionalIterator current;
public:typedef bidirectional_iterator_tag iterator_category;typedef T value_type;typedef Distance difference_type;typedef T* pointer;typedef Reference reference;reverse_bidirectional_iterator() {}explicit reverse_bidirectional_iterator(BidirectionalIterator x): current(x) {}BidirectionalIterator base() const { return current; }Reference operator*() const {BidirectionalIterator tmp = current;return *--tmp;}
#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */self& operator++() {--current;return *this;}self operator++(int) {self tmp = *this;--current;return tmp;}self& operator--() {++current;return *this;}self operator--(int) {self tmp = *this;++current;return tmp;}
};
template <class RandomAccessIterator, class T, class Reference = T&,class Distance = ptrdiff_t>
class reverse_iterator {typedef reverse_iterator<RandomAccessIterator, T, Reference, Distance>self;
protected:RandomAccessIterator current;
public:typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef Distance difference_type;typedef T* pointer;typedef Reference reference;reverse_iterator() {}explicit reverse_iterator(RandomAccessIterator x) : current(x) {}RandomAccessIterator base() const { return current; }Reference operator*() const { return *(current - 1); }
#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */self& operator++() {--current;return *this;}self operator++(int) {self tmp = *this;--current;return tmp;}self& operator--() {++current;return *this;}self operator--(int) {self tmp = *this;++current;return tmp;}self operator+(Distance n) const {return self(current - n);}self& operator+=(Distance n) {current -= n;return *this;}self operator-(Distance n) const {return self(current + n);}self& operator-=(Distance n) {current += n;return *this;}Reference operator[](Distance n) const { return *(*this + n); }
};
#endif //__STL_CLASS_PARTIAL_SPECIALIZATION

? 源碼中我們可以看到reverse_iterator實現了兩個版本，通過
__STL_CLASS_PARTIAL_SPECIALIZATION 條件編譯控制使用哪個版本，在舊版本中，因為因為封裝是類型不好確定，我們需要自己傳遞參數，而有了萃取技術后，我們可以得到對應的類型，因此就不需要傳遞很多參數。

簡單點說就是支持偏特化的迭代器萃取以后，反向迭代器使用的是這個版本， template <class Iterator>class reverse_iterator（一個參數）; 之前使用的是template <class BidirectionalIterator, class T, class Reference,class Distance>class reverse_bidirectional_iterator;template <class RandomAccessIterator, class T, class Reference,class Distance>class reverse_iterator;（多個參數）

? 我們可以看到他們的差別主要是在模板參數是否傳遞迭代器指向的數據類型，支持偏特化的迭代器萃取以后就不需要給了，因為reverse_iterator 內部可以通過迭代器萃取獲取數據類型。迭代器萃取的本質是一個特化（這里我們就不講解了），想了解可以去看源碼。

本文這里我們為了便于理解，我們主要使用模版參數傳遞數據類型的方式實現。

? 反向迭代器本質是一個適配器，使用模版實現，傳遞哪個容器的迭代器就可以封裝適配出對應的反向迭代器。因為反向迭代器的功能跟正向的迭代器功能高度相似，只是遍歷的方向相反，類似operator++ 底層調用迭代器的operator-- 等，所以封裝一下就可以實現。

? 比較奇怪的是operator*的實現，源碼內部訪問的是迭代器當前位置的前一個位置。

這個要結合容器中rbegin和rend實現才能看懂，rbegin返回的是封裝end位置的反向迭代器，rend返回的是封裝begin位置迭代器的反向迭代器，這里是為了與正向迭代器對應，專門實現出一個對稱版本，begin與rend，end與rbegin，所以解引用訪問的是當前位置的前一個位置，這樣返回解引用rbegin時，返回上一個節點，即返回有效節點的最后一個節點，解引用rend就會正好返回哨兵節點。（這里沒有其他的特殊作用，如果愿意也可以不對稱實現）

1.2. 實現反向迭代器

// ReverseIterator.h
// 所有容器的反向迭代器
// 迭代器適配器
namespace zlr
{template<class Iterator, class Ref, class Ptr>struct ReverseIterator{typedef ReverseIterator<Iterator, Ref, Ptr> Self;// 正向迭代器Iterator _it;ReverseIterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}Self operator++(int){Self tmp(*this);--_it;return tmp;}Self operator--(int){Self tmp(*this);--_it;return tmp;}bool operator!=(const Self& s) const{return _it != s._it;}bool operator==(const Self& s) const{return _it != s._it;}};
}
// vector.h
#include"ReverseIterator.h"
namespace zlr
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*>const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}// ....private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};
}
// list.h
#include"ReverseIterator.h"
namespace zlr
{template<class T>class list{typedef ListNode<T> Node;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*>const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}// ...private:Node* _head;size_t _size;};
}
// test.cpp
#include"list.h"
#include"vector.h"
int main()
{zlr::list<int> lt = { 1,2,3,4 };zlr::list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){//*rit = 1;cout << *rit << " ";++rit;}cout << endl;return 0;
}
//int main()
//{
// zlr::vector<int> v = { 1,2,3,4 };
// zlr::vector<int>::reverse_iterator rit = v.rbegin();
// while (rit != v.rend())
// {
// //*rit = 1;
// cout << *rit << " ";
// ++rit;
// }
// cout << endl;
//
// return 0;
//}

2.stack和queue練習拓展-計算器實現

2.1. 后綴表達式概念

? 我們日常寫的計算表達式都是中綴表達式，也就是運算符在中間，運算數在兩邊，但是中綴表達式直接讀取無法馬上進行運算，因為一個計算表達式還涉及運算符優先級問題，中綴表達式無法直接確定一個運算符優先級，必須根據相鄰運算符才能確定。如： 1-2*(3-4)+5 中遇到-和*都無法運算，因為后面還有括號優先級更高。

? 所以其中一種實現思路是把中綴表達式轉換為后綴表達式，也就是說分析計算表達式的優先級，將運算符放到前面，運算符放到運算數的后面，然后我們依次讀取后綴表達式，遇到運算符就可以進行運算了。后綴表達式也就做逆波蘭表達式(Reverse Polish Notation, RPN)，這種表示法由波蘭邏輯學家J·盧卡西維茲于1929年提出，后來被廣泛應用于計算機科學中。

2.2. 后綴表達式運算規則

? 后綴表達式因為已經確定好優先級，運算符方式非常簡單，就是遇到運算符時，取前面的兩個數進行運算，因為經過中綴轉后綴優先級已經確定好了，因此我們根據運算特點，使用棧來實現。

? 建立一個棧存儲運算數，讀取后綴表達式，遇到運算數入棧；遇到運算符，出棧頂的兩個數據進行運算，運算后將結果作為一個運算數入棧繼續參與下一次的運算。讀取表達式結束后，最后棧里面的值就是運算結果。

??? 150. 逆波蘭表達式求值 - 力扣（LeetCode）???????

class Solution {
public:int evalRPN(const vector<string>& tokens) {stack<int> s;for (size_t i = 0; i < tokens.size(); ++i){const string& str = tokens[i];// str為運算數，入棧if (!("+" == str || "-" == str || "*" == str || "/" == str)){s.push(stoi(str));}else{// str為運算符，取前兩個運算數進行運算int right = s.top();s.pop();int left = s.top();s.pop();switch (str[0]){case '+':s.push(left + right);break;case '-':s.push(left - right);break;case '*':s.push(left * right);break;case '/':s.push(left / right);break;}}}return s.top();}
};

2.3. 中綴表達式轉后綴表達式

2.3.1 轉換思路

? 依次讀取計算表達式中的值，遇到運算數直接輸出。

? 建立一個棧存儲運算符，利用棧后進新出性質，遇到后面運算符，出棧里面存的前面運算符進行比較，確定優先級。

? 遇到運算符，如果棧為空或者棧不為空且當前運算符比棧頂運算符優先級高，則當前運算符入棧。因為如果棧里面存儲的是前一個運算符，當前運算符比前一個優先級高，說明前一個不能運算，當前運算符也不能運算，因為后面可能還有更高優先級的運算符。

? 遇到運算符，如果棧不為為空且當前運算符比棧頂運算符優先級低或相等，說明棧頂的運算符可以運算了，則輸出棧頂運算符，當前運算符繼續走前面遇到運算符的邏輯。

? 如果遇到()，則把括號的計算表達式當成一個子表達式，進行遞歸，跟上思路類似處理子表達式，處理后轉換出的后綴表達式加在前面表達式的后面即可。

? 計算表達式或者()中子表達式結束時，輸出棧中所有運算符。

2.3.2 代碼實現

class Solution {
public://map<char, int> _operatorPrecedence = { { '+', 1 }, { '-', 1 }, { '*', 2//}, { '/', 2 } };//因為運算符優先級與ASCII無關，這里我們使用結構體來處理運算符的優先級比較問題//如果學習過map容器，可以使用map處理int operatorPrecedence(char ch){struct opPD{char _op;int _pd;};static opPD arr[] = { {'+', 1},{'-', 1},{'*', 2},{'/', 2} };for (auto& e : arr){if (e._op == ch){return e._pd;}}assert(false);return -1;}//因為有遞歸的情況存在，我們這里使用i來記錄當前訪問位置void toRPN(const string& s, size_t& i, vector<string>& v){stack<char> st;while (i < s.size()){if (isdigit(s[i])){// 操作數輸出string num;while (i < s.size() && isdigit(s[i])){num += s[i];++i;}v.push_back(num);}else{if (s[i] == '('){// 遞歸方式處理括號中的子表達式++i;toRPN(s, i, v);}else if (s[i] == ')'){++i;// 棧中的運算符全部輸出while (!st.empty()){v.push_back(string(1, st.top()));st.pop();}// 結束遞歸return;}else{// 運算符// 1、如果棧為空或者棧不為空且當前運算符比棧頂運算符優先級高，則當//前運算符入棧// 2、如果棧不為為空且比棧頂運算符優先級低或相等，說明棧頂的運算符//可以運算了，// 輸出棧頂運算符，當前運算符繼續走前面遇到運算符的邏輯if (st.empty() || operatorPrecedence(s[i]) >operatorPrecedence(st.top())){st.push(s[i]);++i;}else{v.push_back(string(1, st.top()));st.pop();}}}}// 棧中的運算符全部輸出while (!st.empty()){v.push_back(string(1, st.top()));st.pop();}}
};
int main()
{size_t i = 0;vector<string> v;//string str = "1+2-3";string str = "1+2-(3*4+5)-7";Solution().toRPN(str, i, v);for (auto& e : v){cout << e << " ";}cout << endl;return 0;
}

2.4. 計算器實現

?? 224. 基本計算器 - 力扣（LeetCode）?

? 有了上面兩個部分學習之后，計算器OJ的大部分問題就解決了，但是這里還有一些問題需要處理。因為OJ中給的中綴表達式是字符串，字符串中包含空格，需要去掉空格。

? 其次就是負數和減號，要進行區分，將所有的負數-x轉換為0-x，因為我們實現的代碼考慮到乘除的情況，針對括號內的符號，我們不能直接變號處理。

class Solution {
public://map<char, int> _operatorPrecedence = { { '+', 1 }, { '-', 1 }, { '*', 2
}, { '/', 2 } };
int operatorPrecedence(char ch)
{struct opPD{char _op;int _pd;};static opPD arr[] = { {'+', 1},{'-', 1},{'*', 2},{'/', 2} };for (auto& e : arr){if (e._op == ch){return e._pd;}}assert(false);return -1;
}
void toRPN(const string& s, size_t& i, vector<string>& v)
{stack<char> st;while (i < s.size()){if (isdigit(s[i])){// 運算數輸出string num;while (i < s.size() && isdigit(s[i])){num += s[i];++i;}v.push_back(num);}else{if (s[i] == '('){// 遞歸方式處理括號中的子表達式++i;toRPN(s, i, v);}else if (s[i] == ')'){++i;// 棧中的運算符全部輸出while (!st.empty()){v.push_back(string(1, st.top()));st.pop();}// 結束遞歸return;}else{// 運算符// 1、如果棧為空或者棧不為空且當前運算符比棧頂運算符優先級高，則當//前運算符入棧// 2、如果棧不為為空且比棧頂運算符優先級低或相等，說明棧頂的運算符//可以運算了，// 輸出棧頂運算符，當前運算符繼續走前面遇到運算符的邏輯if (st.empty() || operatorPrecedence(s[i]) >operatorPrecedence(st.top())){st.push(s[i]);++i;}else{v.push_back(string(1, st.top()));st.pop();}}}}// 棧中的運算符全部輸出while (!st.empty()){v.push_back(string(1, st.top()));st.pop();}
}
int evalRPN(const vector<string>& tokens) {stack<int> s;for (size_t i = 0; i < tokens.size(); ++i){const string& str = tokens[i];// str為數字if (!("+" == str || "-" == str || "*" == str || "/" == str)){s.push(stoi(str));}else{// str為操作符int right = s.top();s.pop();int left = s.top();s.pop();switch (str[0]){case '+':s.push(left + right);break;case '-':s.push(left - right);break;case '*':s.push(left * right);break;case '/':s.push(left / right);break;}}}return s.top();
}
int calculate(string s)
{// 1、去除所有空格，否則下面的一些邏輯沒辦法處理std::string news;news.reserve(s.size());for (auto ch : s){if (ch != ' ')news += ch;}s.swap(news);news.clear();// 2、將所有的負數-x轉換為0-xfor (size_t i = 0; i < s.size(); ++i){//當-的前一個字符不為運算數時，我們才添加"0-",否則就是減號，不需要處理//同時因為這里是下標比較，需要注意符號在表達式第一位的情況，防止越界if (s[i] == '-' && (i == 0 || (!isdigit(s[i - 1]) && s[i - 1] !=')')))news += "0-";elsenews += s[i];}// 中綴表達式轉成后綴表達式size_t i = 0;vector<string> v;toRPN(news, i, v);// 后綴表達式進行運算return evalRPN(v);
}
};