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

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

1. 反向迭代器思路 (源码及框架分析)

反向迭代器是一种特殊的迭代器，它的核心作用是：从容器的末尾开始，逆向遍历容器中的元素（正常迭代器是从头部到尾部）。可以把它理解成： 正常迭代器：像你从队伍第一个人走到最后一个人； 反向迭代器：像你从队伍最后一个人倒着走回第一个人。

SGI-STL30 版本源代码，反向迭代器实现的核心源码在 stl_iterator.h 中，反向迭代器是一个适配器，各个容器中再适配出自己的反向迭代器。下面我们截出 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_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
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()); }
};

// 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.
template <class Iterator>
class reverse_iterator {
protected:
    Iterator current;
public:
    typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
    typedef typename iterator_traits<Iterator>::value_type value_type;
    typedef typename iterator_traits<Iterator>::difference_type difference_type;
    typedef typename iterator_traits<Iterator>::pointer pointer;
    typedef typename iterator_traits<Iterator>::reference reference;
    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_TEMPLATE
    template <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_OPERATOR
    pointer 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_OPERATOR
    pointer 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_OPERATOR
    pointer 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

1️⃣ 源码中我们可以看到 reverse_iterator 实现了两个版本，通过 __STL_CLASS_PARTIAL_SPECIALIZATION 条件编译控制使用哪个版本，简单点说就是支持偏特化的迭代器萃取以后，反向迭代器使用的是这个版本 template <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。 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 逆波兰表达式求值

参考题目：https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

// 后缀表达式进行运算
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. 基本计算器的实现

参考题目：https://leetcode.cn/problems/basic-calculator/

有了上面两个部分计算器 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 返回。