C++反向迭代器实现、逆波兰表达式与计算器实现

源码分析要点：

1. 源码中 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 等。
2. 差别主要在于模板参数是否传递迭代器指向的数据类型。支持偏特化的迭代器萃取以后就不需要给了，因为 reverse_iterator 内部可以通过迭代器萃取获取数据类型。
3. 反向迭代器本质上是一个适配器，使用模版实现，传递哪个容器的迭代器就可以封装适配出对应的反向迭代器。因为反向迭代器的功能跟正向的迭代器功能高度相似，只是遍历的方向相反，类似 operator++ 底层调用迭代器的 operator-- 等，所以封装一下就可以实现。
4. 比较奇怪的是 operator* 的实现，内部访问的是迭代器当前位置的前一个位置。这要结合容器中 rbegin 和 rend 实现才能看懂，rbegin 返回的是封装 end 位置的反向迭代器，rend 返回的是封装 begin 位置迭代器的反向迭代器，这里是为了实现出一个对称，所以解引用访问的是当前位置的前一个位置。

2. 反向迭代器的实现

// Common.h - 基础头文件和节点定义
#pragma once
#include <iostream>
#include <cstdlib> // 内存分配
#include <algorithm>
using namespace std;

// List 节点定义（list 依赖）
template<class T>
struct ListNode {
    T _data;
    ListNode<T>* _prev;
    ListNode<T>* _next;
    // 节点构造函数
    ListNode(const T& val = T()) : _data(val), _prev(nullptr), _next(nullptr) {}
};

// 迭代器基础（list 的正向迭代器)
template<class T, class Ref, class Ptr>
struct ListIterator {
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr> Self;
    Node* _node;
    // 构造函数
    ListIterator(Node* node) : _node(node) {}
    // 运算符重载
    Ref operator*() const { return _node->_data; }
    Ptr operator->() const { return &_node->_data; }
    // 前置++
    Self& operator++() { _node = _node->_next; return *this; }
    // 后置++
    Self operator++(int) {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    // 前置--
    Self& operator--() { _node = _node->_prev; return *this; }
    // 后置--
    Self operator--(int) {
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    // 比较运算符
    bool operator==(const Self& s) const { return _node == s._node; }
    bool operator!=(const Self& s) const { return _node != s._node; }
};

// ReverseIterator.h
#pragma once
#include "Common.h"
namespace lcz {
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator {
    typedef ReverseIterator<Iterator, Ref, Ptr> Self;
    // 存储正向迭代器
    Iterator _it;
    // 构造函数
    ReverseIterator(Iterator it) : _it(it) {}
    // 解引用：const 版本 + 非 const 版本（保证 const 正确性）
    Ref operator*() {
        Iterator tmp = _it;
        return *(--tmp); // 反向迭代器解引用 = 正向迭代器退一位
    }
    Ref operator*() const {
        Iterator tmp = _it;
        return *(--tmp);
    }
    // 箭头运算符
    Ptr operator->() { return &(operator*()); }
    Ptr operator->() const { return &(operator*()); }
    // 前置++：反向迭代器++ → 正向迭代器--
    Self& operator++() { --_it; return *this; }
    // 后置++
    Self operator++(int) {
        Self tmp(*this);
        --_it;
        return tmp;
    }
    // 前置--：反向迭代器-- → 正向迭代器++
    Self& operator--() { ++_it; return *this; }
    // 后置--（修复原代码错误：--_it → ++_it）
    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; }
};
} // namespace lcz

// vector.h
#pragma once
#include "ReverseIterator.h"
namespace lcz {
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;
    // 构造函数
    vector() : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {}
    // 初始化列表构造（支持 v = {1,2,3,4}）
    vector(initializer_list<T> il) {
        size_t n = il.size();
        _start = new T[n];
        _finish = _start + n;
        _endofstorage = _finish;
        copy(il.begin(), il.end(), _start);
    }
    // 析构函数
    ~vector() {
        if (_start) {
            delete[] _start;
            _start = _finish = _endofstorage = nullptr;
        }
    }
    // 正向迭代器接口
    iterator begin() { return _start; }
    iterator end() { return _finish; }
    const_iterator begin() const { return _start; }
    const_iterator end() const { return _finish; }
    // 反向迭代器接口
    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()); }
private:
    iterator _start = nullptr; // 数组起始
    iterator _finish = nullptr; // 有效数据末尾
    iterator _endofstorage = nullptr; // 容量末尾
};
} // namespace lcz

// list.h
#pragma once
#include "ReverseIterator.h"
namespace lcz {
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;
    // 构造函数：初始化头节点（双向循环链表）
    list() {
        _head = new Node;
        _head->_prev = _head;
        _head->_next = _head;
        _size = 0;
    }
    // 初始化列表构造（支持 lt = {1,2,3,4}）
    list(initializer_list<T> il) : list() {
        for (const auto& val : il) {
            push_back(val);
        }
    }
    // 析构函数
    ~list() {
        clear();
        delete _head;
        _head = nullptr;
        _size = 0;
    }
    // 尾插（初始化列表依赖）
    void push_back(const T& val) {
        Node* new_node = new Node(val);
        Node* tail = _head->_prev;
        tail->_next = new_node;
        new_node->_prev = tail;
        new_node->_next = _head;
        _head->_prev = new_node;
        _size++;
    }
    // 清空链表
    void clear() {
        iterator it = begin();
        while (it != end()) {
            it = erase(it);
        }
    }
    // 删除节点
    iterator erase(iterator pos) {
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* next = cur->_next;
        prev->_next = next;
        next->_prev = prev;
        delete cur;
        _size--;
        return iterator(next);
    }
    // 正向迭代器接口
    iterator begin() { return iterator(_head->_next); }
    iterator end() { return iterator(_head); }
    const_iterator begin() const { return const_iterator(_head->_next); }
    const_iterator end() const { return const_iterator(_head); }
    // 反向迭代器接口
    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()); }
private:
    Node* _head = nullptr;
    size_t _size = 0;
};
} // namespace lcz

// test.cpp
#include "list.h"
#include "vector.h"
int main() {
    // 测试 list 反向迭代器
    cout << "list 反向遍历：";
    lcz::list<int> lt = {1, 2, 3, 4};
    lcz::list<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend()) {
        cout << *rit << " "; // 输出：4 3 2 1
        ++rit;
    }
    cout << endl;
    // 测试 vector 反向迭代器
    cout << "vector 反向遍历：";
    lcz::vector<int> v = {1, 2, 3, 4};
    lcz::vector<int>::reverse_iterator vit = v.rbegin();
    while (vit != v.rend()) {
        cout << *vit << " "; // 输出：4 3 2 1
        ++vit;
    }
    cout << endl;
    return 0;
}

3. 逆波兰表达式介绍 (也叫后缀表达式)

我们日常写的计算表达式都是中缀表达式，也就是运算符在中间，运算数在两边，但是直接读取无法马上进行运算因为一个计算表达式还涉及运算符优先级问题。如：1-2*(3-4)+5 中遇到 - 和 * 都无法运算，因为后面还有括号优先级更高。所以其中一种实现思路是把中缀表达式转换为后缀表达式，也就是说分析计算表达式的优先级，将运算符放到前面，运算符放到运算数的后面，然后我们依次读取后缀表达式，遇到运算符就可以进行运算了。后缀表达式也就做 逆波兰表达式(Reverse Polish Notation, RPN)，这种表示法由 波兰逻辑学家 J·卢卡西维兹 于 1929 年提出，后来被广泛应用于计算机科学中。

3.1 后缀表达式进行运算

后缀表达式因为已经确定好优先级，运算符方式非常简单，就是遇到运算符时，取前面的两个运算符进行运算，因为经过中缀转后缀优先级已经确定好了。建立一个栈存储运算数，读取后缀表达式，遇到运算数入栈，遇到运算符，出栈顶的两个数据进行运算，运算后将结果作为一个运算数入栈继续参与下一次的运算。读取表达式结束后，最后栈里面的值就是运算结果。

3.2 逆波兰表达式求值

// 后缀表达式进行运算
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (auto str : tokens) {
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                // 运算符，运算，运算结果入栈
                int right = st.top(); st.pop();
                int 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();
    }
};

3.3 中缀表达式转后缀表达式 (含代码实现)

1. 依次读取计算表达式中的值，遇到运算数直接输出。
2. 建立一个栈存储运算符，利用栈后进新出性质，遇到后面运算符，出栈里面存的前面运算符进行比较，确定优先级。
3. 遇到运算符，如果栈为空或者栈不为空且当前运算符比栈顶运算符优先级高，则当前运算符入栈。因为如果栈里面存储的是前一个运算符，当前运算符比前一个优先级高，说明前一个不能运算，当前运算符也不能运算，因为后面可能还有更高优先级的运算符。
4. 遇到运算符，如果栈不为为空且当前运算符比栈顶运算符优先级低或相等，说明栈顶的运算符可以运算了，则输出栈顶运算符，当前运算符继续走前面遇到运算符的逻辑。
5. 如果遇到 ()，则把括号的计算表达式当成一个子表达式，跟上思路类似，进行递归处理子表达式，处理后转换出的后缀表达式加在前面表达式的后面即可。
6. 计算表达式或者 () 中子表达式结束值，输出栈中所有运算符。

#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <cctype>
#include <cassert>
using namespace std;

class Solution {
public:
    // 获取运算符优先级
    int operatorPrecedence(char ch) {
        static const pair<char, int> opPD[] = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
        int n = sizeof(opPD) / sizeof(opPD[0]);
        for (int i = 0; i < n; ++i) {
            if (opPD[i].first == ch) {
                return opPD[i].second;
            }
        }
        assert(false && "非法运算符");
        return -1;
    }
    // 中缀转逆波兰表达式（核心函数，栈作为参数传递，避免递归时重建）
    void toRPN(const string& s, size_t& i, vector<string>& rpn, stack<char>& opStack) {
        while (i < s.size()) {
            if (isdigit(s[i])) {
                // 处理多位数（操作数直接加入结果）
                string num;
                while (i < s.size() && isdigit(s[i])) {
                    num += s[i];
                    ++i;
                }
                rpn.push_back(num);
            } else {
                if (s[i] == '(') {
                    // 左括号入栈，递归处理括号内子表达式
                    opStack.push(s[i]);
                    ++i;
                    toRPN(s, i, rpn, opStack);
                } else if (s[i] == ')') {
                    // 右括号：弹出运算符直到左括号（左括号弹出但不加入结果）
                    ++i;
                    while (!opStack.empty() && opStack.top() != '(') {
                        rpn.push_back(string(1, opStack.top()));
                        opStack.pop();
                    }
                    // 弹出左括号（不加入结果）
                    if (!opStack.empty()) {
                        opStack.pop();
                    }
                    // 结束当前递归层，回到外层处理
                    return;
                } else {
                    // 处理运算符：优先级判断
                    // 栈非空 + 栈顶不是左括号 + 当前运算符优先级 ≤ 栈顶 → 弹出栈顶运算符
                    while (!opStack.empty() && opStack.top() != '(' && operatorPrecedence(s[i]) <= operatorPrecedence(opStack.top())) {
                        rpn.push_back(string(1, opStack.top()));
                        opStack.pop();
                    }
                    // 当前运算符入栈，i 递增（关键：避免死循环）
                    opStack.push(s[i]);
                    ++i;
                }
            }
        }
    }
    // 封装接口：对外提供简洁的调用方式
    vector<string> convertToRPN(const string& s) {
        vector<string> rpn;
        stack<char> opStack;
        size_t i = 0;
        toRPN(s, i, rpn, opStack);
        // 遍历结束后，弹出栈中剩余的运算符
        while (!opStack.empty()) {
            rpn.push_back(string(1, opStack.top()));
            opStack.pop();
        }
        return rpn;
    }
    // 逆波兰表达式求值（可选：验证转换结果是否正确）
    int evalRPN(const vector<string>& rpn) {
        stack<int> st;
        for (const string& token : rpn) {
            if (isdigit(token[0]) || (token.size() > 1 && token[0] == '-' && isdigit(token[1]))) {
                // 处理数字（含负数）
                st.push(stoi(token));
            } else {
                // 处理运算符
                int b = st.top(); st.pop();
                int a = st.top(); st.pop();
                int res = 0;
                if (token == "+") res = a + b;
                else if (token == "-") res = a - b;
                else if (token == "*") res = a * b;
                else if (token == "/") res = a / b; // 整数除法向零取整
                st.push(res);
            }
        }
        return st.top();
    }
};

int main() {
    Solution sol;
    // 测试用例 1：简单表达式
    string str1 = "1+2-3";
    vector<string> rpn1 = sol.convertToRPN(str1);
    cout << "中缀表达式：" << str1 << endl;
    cout << "逆波兰表达式：";
    for (const auto& e : rpn1) {
        cout << e << " "; // 输出：1 2 + 3 -
    }
    cout << endl;
    cout << "计算结果：" << sol.evalRPN(rpn1) << endl; // 输出：0
    cout << "------------------------" << endl;
    // 测试用例 2：带括号的复杂表达式
    string str2 = "1+2-(3*4+5)-7";
    vector<string> rpn2 = sol.convertToRPN(str2);
    cout << "中缀表达式：" << str2 << endl;
    cout << "逆波兰表达式：";
    for (const auto& e : rpn2) {
        cout << e << " "; // 输出：1 2 + 3 4 * 5 + - 7 -
    }
    cout << endl;
    cout << "计算结果：" << sol.evalRPN(rpn2) << endl; // 输出：1+2=3; 3*4=12+5=17; 3-17=-14; -14-7=-21
    return 0;
}

4. 基本计算器的实现

有了上面两个部分计算器 OJ 的大部分问题就解决了，但是这里还有一些问题需要处理。因为 OJ 中给的中缀表达式是字符串，字符串中包含空格，需要去掉空格。其次就是负数和减号，要进行区分，将所有的负数 -x 转换为 0-x。

class Solution {
public:
    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();
        }
    }
    long long evalRPN(const vector<string>& tokens) {
        stack<long long> s;
        for (size_t i = 0; i < tokens.size(); ++i) {
            const string& str = tokens[i];
            // str 为数字
            if (!("+" == str || "-" == str || "*" == str || "/" == str)) {
                s.push(stoll(str));
            } else {
                // str 为操作符
                long long right = s.top(); s.pop();
                long long 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-x
        for (size_t i = 0; i < s.size(); ++i) {
            if (s[i] == '-' && (i == 0 || (!isdigit(s[i - 1]) && s[i - 1] != ')'))) {
                news += "0-";
            } else {
                news += s[i];
            }
        }
        // 中缀表达式转成后缀表达式
        size_t i = 0;
        vector<string> v;
        toRPN(news, i, v);
        // 后缀表达式进行运算
        return evalRPN(v);
    }
};

解题思路

1. 表达式预处理
   • 去除空格：首先去除表达式中的所有空格，简化后续处理逻辑。
   • 负数特殊处理：对于出现在表达式开头或左括号后的负号，需要特殊处理。例如，将 "-x" 转换为 "0-x"，但为了避免溢出，我们直接将整个负数作为一个完整的数字解析 (如 "-2147483648" 作为一个整体)。
2. 中缀表达式转后缀表达式 (逆波兰表达式)
   • 使用递归下降法：由于括号会改变运算顺序，我们使用递归的方式处理括号内的子表达式。具体地，遇到左括号时递归处理，直到遇到右括号返回。
   • 运算符优先级：设置加减为 1 级，乘除为 2 级。在转换过程中，如果当前运算符优先级高于栈顶运算符，则入栈；否则将栈顶运算符弹出并加入后缀表达式，直到栈空或遇到更低优先级的运算符。
   • 数字直接输出：遇到数字时，将连续的数字字符拼接成一个完整的数字字符串，直接加入后缀表达式。
3. 后缀表达式求值
   • 使用栈模拟：遍历后缀表达式，遇到数字则压栈，遇到运算符则弹出栈顶两个数字进行运算，并将结果压栈。
   • 处理大数：由于可能涉及边界值 (如 -2147483648)，使用 long long 类型进行计算，避免溢出。最后将结果转换为 int 返回。