【C++笔记】反向迭代器和计算器的思路分析及其实现

🕗 发布于 2025-01-20 02:28 c++ 笔记 开发语言

【C++笔记】反向迭代器和计算器的思路分析及其实现

🔥个人主页：大白的编程日记

🔥专栏：C++笔记

文章目录

【C++笔记】反向迭代器和计算器的思路分析及其实现

前言

哈喽，各位小伙伴大家好!上期我们讲了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;
    }
};

在这里插入图片描述

后言

这就是反向迭代器和计算器的思路分析及其实现。大家自己好好消化！今天就分享到这！感谢各位的耐心垂阅！咱们下期见！拜拜~

原文地址：https://blog.csdn.net/2301_81670477/article/details/144783687

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Visual Studio Code 配置 java/maven 环境(Windows版)
下一篇：已解决java.sql.SQLNonTransientConnectionException: SQL非瞬态连接异常的正确解决方法，亲测有效！！！

mysql之联合索引
联合索引的最左原则索引并非越多越好，过多的索引会增加数据的维护速度还有磁盘空间的浪费。当表的数据量很大的时候，可以考虑建立索引。表中经常查数据的字段，可以考虑建立索引。想要保证表中数据的唯一性，可以考
阅读更多2025-01-20
【HarmonyOS NAPI 深度探索10】HarmonyOS Next 中的 NAPI 的架构与原理
NAPI在HarmonyOSNext中扮演着核心角色，它通过统一的接口封装，实现了JavaScript和C/C++之间的高效交互。无论是其架构的精巧设计，还是内存管理和异步处理的细致考虑，都为开发者提
阅读更多2025-01-20
【Unity3D】远处的物体会闪烁问题(深度冲突) Reversed-Z
因为深度值是浮点类型float32，其浮点数记录无法保证精确度的，它仅有23个二进制有效位保存数据，8位是指数位，1位是符号位，其中23位只是小数有效位，若只谈纯整数它有24位有效位，2^24代表16
阅读更多2025-01-20
国产编辑器EverEdit - 合并行
在编写代码或其他场景下，有时需要把多行的内容缩减成一行，或者纯粹减少行数进行合并，比如：下面的字典的定义，每个元素占了一行，有点浪费，现在需要把它们缩减行数。
阅读更多2025-01-20
归并延拓：LeetCode归并排序逆序对问题
如果您渴望探索更多精心挑选的高频LeetCode面试题，以及它们背后的巧妙解法，欢迎您访问我的博客，那里有我精心准备的一系列文章，旨在帮助技术爱好者们提升算法能力与编程技巧。👉更多高频有趣LeetCo
阅读更多2025-01-20
网络Web存储之LocalStorage
是HTML5提供的一种客户端存储机制，属于Web存储API的一部分。它允许网页在用户的浏览器中存储键值对数据，这些数据会以持久化的方式保存，除非用户手动清除浏览器缓存，或者通过JavaScript代码
阅读更多2025-01-20
Linux中的基本指令（一）
本文主要介绍了Linux中的几个基本指令，包括ls，mkdir，touch，pwd，cd，rmdir，rm，man，cp以及其他的简单指令，如tree，nano，cat，ll等，同时补充了在Linux
阅读更多2025-01-20
大模型在特定行业应用
3. **Qwen系列**：由阿里云研发，这个系列的大模型在电商、金融、广告等多个领域都有应用。企业在选择模型时，通常会考虑模型在目标行业中的应用案例和性能表现。4. **腾讯混元系列**：腾讯推出的
阅读更多2025-01-20
Nginx关于servername配置无效的处理
return403;#拒绝未匹配请求，或者返回自定义响应。发现配置的server_name随便填什么都可以访问前端静态文件。的值实际上不起作用，所有通过IP访问的请求都会被路由到这个。，Nginx默认
阅读更多2025-01-20
在 Windows 下利用 `.pem` 文件配置 VS Code Remote-SSH 连接远程服务器
在日常开发中，使用VSCode的Remote-SSH插件可以方便地通过SSH连接远程服务器，实现本地开发与调试的无缝衔接。然而，在Windows系统下，如果使用`.pem`私钥文件，配置过程中可能会遇
阅读更多2025-01-20

【C++笔记】反向迭代器和计算器的思路分析及其实现