【C++笔记】反向迭代器和计算器的思路分析及其实现
【C++笔记】反向迭代器和计算器的思路分析及其实现
🔥个人主页：大白的编程日记
🔥专栏：C++笔记
文章目录
- 【C++笔记】反向迭代器和计算器的思路分析及其实现
- 前言
- 一.反向迭代器
- 1.1 源码及框架分析
- 1.2 思路分析
- 1.3反向迭代器实现
- 二.计算器
- 2.1 后缀表达式计算(逆波兰表达式)
- 2.2 后缀表达式进行运算
- 2.3 中缀表达式转后缀表达式
- 2.4 计算器实现
- 后言
前言
哈喽，各位小伙伴大家好!上期我们讲了AVL树的深度剖析 。今天我们来讲一下反向迭代器和计算器的实现。话不多说，我们进入正题！向大厂冲锋
一.反向迭代器
1.1 源码及框架分析
SGI-STL30版本源代码，反向迭代器实现的核心源码在stl_iterator.h中，反向迭代器是⼀个适配器，各个容器中再适配出自己的反向迭代器。下面我们截出vector和list的的反向迭代器结构框架核心部分截取出来如下：
- stl_list.h
// 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_SPECIALIZATION
typedef 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 {
return
const_reverse_iterator(end());
}
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const {
return
const_reverse_iterator(begin());
}
};
- stl_vector.h
// stl_vector.h
template <class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator;
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
typedef 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 {
return
const_reverse_iterator(end());
}
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const {
return
const_reverse_iterator(begin());
}
};
这里我们可以看到源码的里面有有三个模版参数的反向迭代器和一个模版参数的反向迭代器。通过宏编译来确定用那个版本的版本的反向迭代器。
1.2 思路分析
大家想一下，反向迭代器和正向迭代器的区别在哪。
反向迭代器本质是⼀个适配器，使用模版实现，传递哪个容器的迭代器就可以封装适配出对应的反向迭代器。因为反向迭代器的功能跟正向的迭代器功能高度相似，只是遍历的方向相反，类似operator++ 底层调用迭代器的 operator-- 等，所以封装⼀下就可以实现。
所以我们可以通过封装正向迭代器适配出反向迭代器。
因为每个容器都有迭代器。
那为什么有三个模版参数和一个模版参数的版本呢？
1.3反向迭代器实现
- 迭代器结构
这里我们用三个模版参数来实现。
这里封装正向迭代器来实现反向迭代器。
template<class iterator,class Ref,class Ptr>
class ReverseIterator
{
public:
using self = ReverseIterator<iterator, Ref, Ptr>;
ReverseIterator(iterator it)
:_it(it)
{}
private:
iterator _it;
};
- begin和end
这里为了逻辑对称，我们可以让rbeing和rend的位置放在begin和end交换后的位置。
同时每次先访问–rbegin的位置即可。
适配list：
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());
}
适配vector:
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
reverse_iterator rbegin()
{
return end();
}
reverse_iterator rend()
{
return begin();
}
- ++和- -
这里直接复用正向迭代器的++和- -即可
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;
}
- operator和operator->
这里返回opertoar返回迭代器的前一个位置即可。
这里需要注意的是为了适配双向和随机迭代器。
这里不能用-。所以我们只能先拷贝一份迭代器再- -。
opertator->复用operator*。
Ref operator*()//对称返回前一位置
{
iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
return &(operator*());
}
-
operator==和operator!=
这里也复用正向迭代器的operator==好operator!=即可。
bool operator!=(const self& t) const
{
return _it != t._it;
}
bool operator==(const self& t) const
{
return _it == t._it;
}
- 测试
二.计算器
2.1 后缀表达式计算(逆波兰表达式)
我们日常写的计算表达式都是中缀表达式，也就是运算符在中间，运算数在两边，但是直接读取无法马上进行运算因为⼀个计算表达式还涉及运算符优先级问题。
如： 1-2*(3-4)+5 中遇到-和*都无法运算，因为后面还有括号优先级更高。
- 中缀转后缀
所以其中⼀种实现思路是把中缀表达式转换为后缀表达式，也就是说分析计算表达式的优先级，将运算符放到前面，运算符放到运算数的后面，然后我们依次读取后缀表达式，遇到运算符就可以进行运算了。后缀表达式也就做逆波兰表达式(Reverse Polish Notation, RPN)，这种表示法由波兰逻辑学家J·卢卡西维兹于1929年提出，后来被广泛应用于计算机科学中。
2.2 后缀表达式进行运算
后缀表达式因为已经确定好优先级，运算符方式非常简单，就是遇到运算符时，取前面的两个运算符进行运算，因为经过中缀转后缀优先级已经确定好了。
- 思路分析
建立⼀个栈存储运算数，读取后缀表达式，遇到运算数入栈，遇到运算符，出栈顶的两个数据进行运算，运算后将结果作为⼀个运算数入栈继续参与下⼀次的运算。读取表达式结束后，最后栈里面的值就是运算结果。
- 代码实现及其应用
题目：逆波兰表达式求值
class Solution {
public:
int evalRPN(vector<string>& tokens)
{
stack<int> s;
for(auto& x:tokens)
{
if(x!="+"&&x!="-"&&x!="*"&&x!="/")//运算数
{
s.push(stoi(x));
}
else//运算符
{
int right,left;
right=s.top();
s.pop();
left=s.top();
s.pop();
switch(x[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 中缀表达式转后缀表达式
转化思路如下：
-
依次读取计算表达式中的值，遇到运算数直接输出。
-
建立⼀个栈存储运算符，利用栈后进新出性质，遇到后面运算符，出栈里面存的前面运算符进行比较，确定优先级。
-
遇到运算符，如果栈为空或者栈不为空且当前运算符比栈顶运算符优先级高，则当前运算符入栈。因为如果栈里面存储的是前⼀个运算符，当前运算符比前⼀个优先级高，说明前⼀个不能运算，当前运算符也不能运算，因为后面可能还有更高优先级的运算符。
-
遇到运算符，如果栈不为为空且当前运算符比栈顶运算符优先级低或相等，说明栈顶的运算符可以运算了，则输出栈顶运算符，当前运算符继续走前面遇到运算符的逻辑。
-
如果遇到()，则把括号的计算表达式当成⼀个子表达式，跟上思路类似，进行递归处理子表达式，处理后转换出的后缀表达式加在前面表达式的后⾯即可。
-
计算表达式或者()中子表达式结束值，输出栈中所有运算符。
确定优先级我们可以用map的键值对来实现。
int operatorPrecedence(char ch)
{
map<char, int> hash = { {'+',1},{'-',1} ,{'*',2} ,{'/',2} };
return hash[ch];
}
- 代码实现
class calculator
{
public:
int operatorPrecedence(char ch)//确定优先级
{
map<char, int> hash = { {'+',1},{'-',1} ,{'*',2} ,{'/',2} };
return hash[ch];
}
void toRPN(string s, size_t& i, vector<string>& v)
{
stack<char> st;
int n = s.size();
while(i<n)
{
/*if (isdigit(s[i]))
{
v.push_back(string(1,s[i]));
i++;
}*/
if (isdigit(s[i]))
{
string num;
while (i < n && isdigit(s[i]))
{
num += s[i++];
}
v.push_back(num);
}
else if (s[i] == '(')//左括号递归表达式
{
i++;
toRPN(s, i, v);
}
else if (s[i] == ')')//右括号return结束递归
{
i++;
while (!st.empty())
{
char ch = st.top();
st.pop();
v.push_back(string(1,ch));
}
return;
}
else
{
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())//弹出栈顶元素
{
char ch = st.top();
st.pop();
v.push_back(string(1, ch));
}
}
};
2.4 计算器实现
知道了逆波兰表达式的计算和中缀转后缀表达式。
我们就可以实现出一个计算器了。
-
题目
题目：基本计算器
-
思路分析
class Solution {
public:
int evalRPN(vector<string>& tokens)
{
stack<int> s;
for(auto& x:tokens)
{
if(x!="+"&&x!="-"&&x!="*"&&x!="/")
{
s.push(stoi(x));
}
else
{
int right,left;
right=s.top();
s.pop();
left=s.top();
s.pop();
switch(x[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 operatorPrecedence(char ch)
{
map<char, int> hash = { {'+',1},{'-',1} ,{'*',2} ,{'/',2} };
return hash[ch];
}
void toRPN(string s, size_t& i, vector<string>& v)
{
stack<char> st;
int n = s.size();
while(i<n)
{
/*if (isdigit(s[i]))
{
v.push_back(string(1,s[i]));
i++;
}*/
if (isdigit(s[i]))
{
string num;
while (i < n && isdigit(s[i]))
{
num += s[i++];
}
v.push_back(num);
}
else if (s[i] == '(')
{
i++;
toRPN(s, i, v);
}
else if (s[i] == ')')
{
i++;
while (!st.empty())
{
char ch = st.top();
st.pop();
v.push_back(string(1,ch));
}
return;
}
else
{
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())
{
char ch = st.top();
st.pop();
v.push_back(string(1, ch));
}
}
int calculate(string s)
{
string t;
for(auto& x:s)
{
if(x!=' ')//跳过空格构建新串
{
t+=x;
}
}
cout<<t<<endl;
string t1;
for(int i=0;i<t.size();i++)
{
if(t[i]=='-'&&(i==0||(!isdigit(t[i-1])&&t[i-1]!=')')))//判断是负数还是操作符
{
t1+="0-";
}
else
{
t1+=t[i];
}
}
cout<<t1;
size_t i=0;
vector<string> s1;//
toRPN(t1,i,s1);//中缀转后缀
return evalRPN(s1);//逆波兰表达式求值
}
};
但是这道题还有更简单的解法。
-
思路分析
-
代码实现
class Solution {
public:
int calculate(string s) {
int begin = 0;
return calHelper(s, begin);
}
int calHelper(string s, int& i) //i用于记录计算开始的索引
{
char operation = '+';
stack<int> nums;
int num = 0;
int res = 0;
bool flag = false;
for (i; i < s.size(); i++)
{
if (isdigit(s[i]))
{
num = num * 10 + (s[i] - '0');
cout<<i<<" ";
}
if (s[i] == '(')
{
num = calHelper(s, ++ i); //从i的下一个开始计算， 进入递归
i++; //计算完之后的i指向)所以再++
}
//保留num
if (((s[i] < '0' || s[i] > '9') && s[i] != ' ') || i == s.size() - 1) // 继续计算
{
int pre = 0;
switch (operation)
{
case '+':
nums.push(num);
break;
case '-':
nums.push(-num);
break;
case '*':
pre = nums.top();
nums.pop();
nums.push(pre * num);
break;
case '/':
pre = nums.top();
nums.pop();
nums.push(pre / num);
break;
}
operation=s[i];
num = 0;//如果没有操作数遇到- 0-num
}
if (s[i] == ')') //遇到)回到上一级递归
{
break;
}
}
while (!nums.empty())
{
res += nums.top();
nums.pop();
}
return res;
}
};
后言
这就是反向迭代器和计算器的思路分析及其实现。大家自己好好消化！今天就分享到这！感谢各位的耐心垂阅！咱们下期见！拜拜~
