【C++】逆波兰表达式 + 反向迭代器的实现

文章目录

📖前言

本章将在上一章栈的基础上进一步讲一个典型栈的应用，逆波兰表达式，再综合之前讲的容器，介绍一下反向迭代器的使用和模拟实现…

1. 逆波兰表达式

1.1 什么是逆波兰表达式：

补充：

• 中缀表达式：

我们平时写的计算手写的都是中缀表达式，也就是形如两个数中间是运算符号的这种。

形如：1 + 3 * 2 - 5，这种就是中缀表达式。

• 后缀表达式：

操作数的顺序不变，但是操作符的顺序变了 – 按照优先级排
后缀表达式是运算符在后面的表达式，中缀表达式是给人来计算的，但是计算机是不能用中缀表达式来计算的，因为没有办法进行运算，表达式的运算涉及到优先级的问题，所以电脑采用的是后缀表达式。

形如：1 3 2 * + 5 -，这种就是后缀表达式。

• 没有前缀表达式：

//……

“逆波兰表达式” 其实就是 “后缀表达式”

1.2 中缀表达式转后缀表达式的过程：

既然我们已经知道了什么是中缀表达式，什么是逆波兰表达式（后缀表达式），那么中缀转后缀该如何进行呢？

我们有固定的一套逻辑：

1. 遇到操作数，输出/存储
2. 遇到操作符，跟栈顶操作符比较

• a.栈为空或者比栈顶优先级高 – 入栈
• b.比栈顶运算符优先级低或者一样 – 出栈顶操作符 -->然后跳到2、继续比较（依次再执行a. b.）
• 后一个运算符来确定前一个运算符的优先级
• 最后将栈中操作符全部出栈

流程图如下：

例题：

• 举个栗子（1） 中缀表达式：1 + 2 * 3 后缀表达式：1 2 3 * +
• 举个栗子（2） 中缀表达式：1 + 2 * 3 / 2 - 5 后缀表达式：1 2 3 * 2 / + 5 -

遇到括号的情况应当将括号中的运算符看作优先级高的运算符，按照高优先级的方式入栈。

• 举个栗子（3） 中缀表达式：1 + 2 * (3 + 4) 后缀表达式：1 2 3 4 + * +

核心：当前运算符不能直接出，后面的运算符有可能比它还要高。

1.3 逆波兰表达式的计算过程：

上述讲了如何由普通的中缀表达式转为逆波兰表达式，那么我们拿到逆波兰表达式该如何计算呢？

这里我们用到了一个数据结构 —— 栈，逆波兰表达式是栈最经典的运用。

我们同样有固定的一套逻辑：

1. 操作数，入栈
2. 操作符，取连续两个栈顶数据运算，运算结果继续入栈，最后的结果就在栈里面

上述逻辑充分结合了栈的结构特点和后缀表达式的特点，下面我们来看一道题：

逆波兰表达式求值：

思路很简单，按照上述逻辑求解即可：

代码如下：

classSolution{public://如果是操作数就入栈，如果是操作符就出栈intevalRPN(vector<string>& tokens){
        stack<longlong> st;for(auto str : tokens){if(str =="+"|| str =="-"|| str =="*"|| str =="/"){longlong right = st.top();
                   st.pop();longlong left = st.top();
                   st.pop();switch(str[0]){case'+':
                       st.push(left + right);break;case'-':
                       st.push(left - right);break;case'*':
                       st.push(left * right);break;case'/':
                       st.push(left / right);break;default:break;}}else{
                   st.push(stoi(str));}}return st.top();}};

2. 反向迭代器（适配器模式）

以我们正常的思路，实现反向迭代器要再单独实现一个反向迭代器的类，但是stl的原码并不是这样实现的。

反向迭代器和正向迭代器相比，除了 ++ 和 – 时方向相反，其他操作基本一致。

• STL在设计反向迭代器的时候是站在了一个顶层来设计
• 因为我们之前学了那么多容器，如果我们每一个容器都要实现一个自己的反向迭代器的话
• 未免会有代码的重复和冗余
• 所以STL设计的时候采用的是一个适配器模式传正向迭代器适配生成反向迭代器，所有的容器都是这么实现反向迭代器的！！

2.1 STL库中的反向迭代器的实现：

反向迭代器的 + + ，就是正向迭代器的 - -

2.2 STL中list的反向迭代器：

• rbegin()是用end()来构造的
• rend()是用begin()来构造的

运用了对称设计的思路：

2.3 STL中vector的反向迭代器：

• 反向迭代器里面，包一个正向迭代器
• 反向迭代器：跟正向迭代器相比，除了 + + 和 - - 时方向相反，其他操作基本一致
• 用一个正向迭代器可以构造一个反向迭代器
• 反向迭代器的 ++ ，里面封了一个正向迭代器的 - -

2.4 Reverseiterator 的模拟实现：

namespace YY
{template<classIterator,classRef,classPtr>structReverse_iterator{
        Iterator _it;typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Reverse_iterator(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;}booloperator!=(const Self& s){return _it != s._it;}};}

• 这里的核心点：用到了适配器模式。
• 只需要在其他容器中适配一下这个反向迭代器即可
• 代码的复用性很强