C++ LeetCode 算法题解析：逆波兰表达式与滑动窗口 | 极客日志

C++算法

C++ LeetCode 算法题解析：逆波兰表达式与滑动窗口

四道 C++ LeetCode 算法题的解法。包括使用栈计算逆波兰表达式求值，利用优先队列和单调队列解决滑动窗口最大值问题，通过哈希表配合最小堆获取前 K 个高频元素，以及使用栈简化 Unix 风格文件路径。内容涵盖数据结构应用与字符串处理技巧。

内存管理发布于 2026/3/24更新于 2026/4/184 浏览

C++ LeetCode 算法题解析：逆波兰表达式与滑动窗口

150 逆波兰表达式求值

给你一个字符串数组 tokens，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/'。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

后缀表达式求值是前后中里面最简单的。

class Solution {
public:
    stack<int> data;
    int evalRPN(vector<string>& tokens) {
        int ans;
        int source1, source2;
        for (string str : tokens) {
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                source1 = data.top(); data.pop();
                source2 = data.top(); data.pop();
                if(str == "+") data.push(source1 + source2);
                if(str == "-") data.push(source2 - source1);
                if(str == "*") data.push(source1 * source2);
                if(str == "/") data.push(source2 / source1);
            }  {
                data.((str));
            }
        }
         data.();
    }
};

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int length = nums.size();
        priority_queue<pair<int, int>> maxheap;
        for (int i = 0; i < k; i++) {
            maxheap.push({nums[i], i});
        }
        int left = 0, right = k;
        vector<int> res;
        res.emplace_back(maxheap.top().first);
        while (right < length) {
            left++;
            if (right != length) maxheap.push({nums[right], right});
            right++;
            while (!maxheap.empty() && maxheap.top().second < left) {
                maxheap.pop();
            }
            res.emplace_back(maxheap.top().first);
        }
        return res;
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int length = nums.size();
        vector<int> res;
        deque<int> q;
        for (int i = 0; i < length; i++) {
            while (!q.empty() && nums[q.back()] < nums[i]) {
                q.pop_back();
            }
            q.push_back(i);
            if (q.front() < i - k + 1) q.pop_front();
            if (i >= k - 1) res.emplace_back(nums[q.front()]);
        }
        return res;
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;
        unordered_map<int, int> m;
        using Node = pair<int, int>; // frequency, element.
        priority_queue<Node, vector<Node>, greater<Node>> q;
        for (int num : nums) {
            m[num] += 1;
        }
        for (auto it = m.begin(); it != m.end(); it++) {
            q.push({it->second, it->first});
            if (q.size() > k) q.pop();
        }
        while (!q.empty()) {
            res.emplace_back(q.top().second);
            q.pop();
        }
        return res;
    }
};

class Solution {
public:
    string simplifyPath(string path) {
        int length = path.size();
        if (length > 0 && path[length - 1] == '/') path.erase(length - 1, 1);
        for (int i = 0; i < path.size(); i++) {
            if (i > 0 && path[i] == '/' && path[i - 1] == '/') {
                path.erase(i - 1, 1);
                i--;
            }
        }
        stack<string> s;
        int start = 0, end = 0;
        int newlength = path.size();
        for (int i = 0; i < newlength; i++) {
            if (path[i] == '/') start = i;
            if (i == newlength - 1 || path[i + 1] == '/') end = i;
            if (start < end) {
                string sub = path.substr(start, end - start + 1);
                if (sub == "/.") { // nop.
                } else if (sub == "/..") {
                    if (!s.empty()) {
                        s.pop();
                    }
                } else {
                    s.push(sub);
                }
            }
        }
        string res;
        while (!s.empty()) {
            res = s.top() + res;
            s.pop();
        }
        if (res == "") return "/";
        return res;
    }
};