C++算法
C++反向迭代器实现、逆波兰表达式与计算器实现
C++反向迭代器基于适配器模式实现容器逆向遍历，核心在于对正向迭代器的包装与重载。逆波兰表达式（后缀表达式）通过栈结构消除运算符优先级歧义，支持中缀转后缀及求值。文章详解反向迭代器源码框架、自定义实现，并包含中缀表达式转后缀算法及处理空格、负数、括号的计算器完整代码逻辑。
C++反向迭代器基于适配器模式实现容器逆向遍历，核心在于对正向迭代器的包装与重载。逆波兰表达式（后缀表达式）通过栈结构消除运算符优先级歧义，支持中缀转后缀及求值。文章详解反向迭代器源码框架、自定义实现，并包含中缀表达式转后缀算法及处理空格、负数、括号的计算器完整代码逻辑。
反向迭代器是一种特殊的迭代器，核心作用是从容器的末尾开始逆向遍历元素（正常迭代器是从头部到尾部）。可以理解为：
SGI-STL 30 版本源代码中，反向迭代器实现的核⼼在 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.
// The class reverse_bidirectional_iterator is no longer part of the draft
// standard, but it is retained for backward compatibility.
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
源码分析要点：
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 等。reverse_iterator 内部可以通过迭代器萃取获取数据类型。operator++ 底层调用迭代器的 operator-- 等，所以封装一下就可以实现。operator* 的实现，内部访问的是迭代器当前位置的前一个位置。这要结合容器中 rbegin 和 rend 实现才能看懂，rbegin 返回的是封装 end 位置的反向迭代器，rend 返回的是封装 begin 位置迭代器的反向迭代器，这里是为了实现出一个对称，所以解引用访问的是当前位置的前一个位置。// 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;
}
我们日常写的计算表达式都是中缀表达式，也就是运算符在中间，运算数在两边，但是直接读取无法马上进行运算因为一个计算表达式还涉及运算符优先级问题。如：1-2*(3-4)+5 中遇到 - 和 * 都无法运算，因为后面还有括号优先级更高。所以其中一种实现思路是把中缀表达式转换为后缀表达式，也就是说分析计算表达式的优先级，将运算符放到前面，运算符放到运算数的后面，然后我们依次读取后缀表达式，遇到运算符就可以进行运算了。后缀表达式也就做 逆波兰表达式(Reverse Polish Notation, RPN)，这种表示法由 波兰逻辑学家 J·卢卡西维兹 于 1929 年提出，后来被广泛应用于计算机科学中。
后缀表达式因为已经确定好优先级，运算符方式非常简单，就是遇到运算符时，取前面的两个运算符进行运算，因为经过中缀转后缀优先级已经确定好了。建立一个栈存储运算数，读取后缀表达式，遇到运算数入栈，遇到运算符，出栈顶的两个数据进行运算，运算后将结果作为一个运算数入栈继续参与下一次的运算。读取表达式结束后，最后栈里面的值就是运算结果。
// 后缀表达式进行运算
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();
}
};
()，则把括号的计算表达式当成一个子表达式，跟上思路类似，进行递归处理子表达式，处理后转换出的后缀表达式加在前面表达式的后面即可。() 中子表达式结束值，输出栈中所有运算符。#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;
}
有了上面两个部分计算器 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);
}
};
解题思路
"-x" 转换为 "0-x"，但为了避免溢出，我们直接将整个负数作为一个完整的数字解析 (如 "-2147483648" 作为一个整体)。-2147483648)，使用 long long 类型进行计算，避免溢出。最后将结果转换为 int 返回。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online