表达式类算法题小结

Heier 发布于2019-08-16 10:32 / 890人阅读

摘要：将表达式转换为逆波兰式，然后求值转换中缀表达式为逆波兰式鲁棒性检测，表达式中没有操作数计算逆波兰式值参考

表达式类算法题小结

[TOC]

声明

文章均为本人技术笔记，转载请注明出处：
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

表达式分类

根据运算符与相关操作操作数的位置不同，将表达式分为前缀，中缀和后缀表达式；

前缀表达式(prefix)：又称波兰式(polish)，运算符位于相关操作数之前；

中缀表示式(infix)：运算符位于相关操作数之间，是通用的表达式记法；计算机计算中缀表达式，一般先将中缀表达式转换为前缀或后缀表达式，然后再求值；

后缀表达式(postfix)：又称逆波兰式(reverse polish)，运算符位于相关操作数之后；逆波兰式与前缀表达式是逆序关系；

lintcode：求逆波兰（后缀）表达式值

当一个表达式以逆波兰式给出，无需考虑运算符优先级

假设给出逆波兰式合法，从左到右挨个扫描逆波兰式，

遇到数字，入栈；

遇到运算符，出栈相关操作数（加减乘除运算出栈2个操作数，自增自减出栈1个操作数）

加减乘除：第一个出栈元素为first, 第二个出栈元素为second，计算second op first，将计算结果入栈

自增自减：栈顶元素出栈，计算first++或first--，将计算结果入栈（阿里2017实习生算法题考点）；

假设给出逆波兰式不保证合法，需检查除法出栈的第一个元素是否为0，检查遇到运算符时栈内元素数目是否满足要求（阿里2017实习生算法题考点）；

复杂度分析：

时间复杂度为$O(N)$，空间复杂度辅助栈占用空间为$O(N)$$；

/**
 * 逆波兰表达式 or 后缀表达式求值
 * http://www.lintcode.com/en/problem/evaluate-reverse-polish-notation/
 * @author yzwall
 */
class Solution {
    public int evalRPN(String[] tokens) {
        ArrayDeque stack = new ArrayDeque<>();
        String Operations = "+-*/";
        for (String token : tokens) {
            if (!Operations.contains(token)) {
                stack.push(Integer.parseInt(token));
                continue;
            }
            int first = stack.pop();
            int second = stack.pop();
            if (token.equals("+")) {
                stack.push(second + first);
            } else if (token.equals("-")) {
                stack.push(second - first);
            } else if (token.equals("*")) {
                stack.push(second * first);
            } else {
                stack.push(second / first);
            }
        }
        return stack.pop();
    }
}

lincode：将中缀表达式转换为逆波兰表达式

中缀表达式符合人类表达逻辑，运算符有优先级，除加减乘除运算外还有左右括号。用一个栈stack只负责存储中缀表达式中的运算符号（右括号)不入栈）：

规定运算符优先级：规定加减运算优先级相等且最低，左右括号优先级相等且最高，乘除优先级相等介于中间；

转换时从左往右扫描表达式，

空栈时，符号直接入栈；

栈不空时，
4.1 当前符号为右括号）：运算符栈一直出栈到逆波兰式，直到栈顶为左括号(或者空栈；栈顶为左括号时，pop掉不加入逆波兰式（bug点）；

4.2 当前符号为其他符号：优先级<=栈顶运算符优先级（bug点），运算符栈一直出栈到栈顶运算符优先级低于当前符号或者空栈；优先级>栈顶运算符优先级，直接入栈，

表达式扫描完毕后，如果栈不空将全部符号出栈到逆波兰式；

复杂度分析

时间复杂度为$O(N)$，空间复杂度辅助栈占用空间为$O(N)$

/**
 * 将（中缀）表达式转换为逆波兰式（去掉括号）
 * http://www.lintcode.com/zh-cn/problem/convert-expression-to-reverse-polish-notation/
 * @author yzwall
 */
class Solution {
    ArrayList convertToRPN(String[] expression) {
        // 鲁棒性检测
        ArrayList postfix = new ArrayList<>();
        if (expression == null || expression.length == 0) {
            return postfix;
        }
        
        // 规定运算符优先级
        HashMap op = new HashMap<>();
        op.put("+", 1);
        op.put("-", 1);
        op.put("*", 2);
        op.put("/", 2);
        op.put("(", 3);
        op.put(")", 3);
        
        // stack为运算符号栈
        ArrayDeque stack = new ArrayDeque<>();
        for (String token : expression) {
            // 数字直接输出到逆波兰式
            if (!op.containsKey(token)) {
                postfix.add(token);
                continue;
            }
            if (!stack.isEmpty()) {
                // 遇到右括号，一直出栈（输出到逆波兰式）到栈顶为左括号或空栈
                if (token.equals(")")) {
                    while (!stack.isEmpty()) {
                        if (stack.peek().equals("(")) {
                            stack.pop();
                            break;
                        }
                        postfix.add(stack.pop());
                    }
                // 当前符号优先级低于栈顶符号，一直出栈到栈顶符号优先级低于当前符号或空栈
                } else if (op.get(stack.peek()) >= op.get(token)) {
                    while (!stack.isEmpty() && op.get(stack.peek()) >= op.get(token)) {
                        // 左括号只有token为右空号时才出栈
                        if (stack.peek().equals("(")) {
                            break;
                        }
                        postfix.add(stack.pop());
                    }
                    stack.push(token);
                } else { // 当前符号优先级高于栈顶符号，直接入栈
                    stack.push(token);
                }
            } else {
                // 空栈，直接入栈
                stack.push(token);
            }
        }
        
        // 表达式扫描完毕，将栈内符号全部出栈到逆波兰式
        while (!stack.isEmpty()) {
            postfix.add(stack.pop());
        }        
        
        return postfix;
    }
}

lintcode：求（中缀）表达式值 解题思路

将（中缀）表达式转换为逆波兰式；

求转换后的逆波兰式值；

注意：表达式中可能一个操作数都没有，在进行2.之前进行鲁棒性检测，比如极端样例
["(","(","(","(","(",")",")",")",")",")"]答案为0；

/**
 * 给出（中缀）表达式，求表达值。将表达式转换为逆波兰式，然后求值
 * http://www.lintcode.com/en/problem/expression-evaluation/
 * @author yzwall
 */
class Solution {
    public int evaluateExpression(String[] expression) {
        int result = 0;
        if (expression == null || expression.length == 0) {
            return result;
        }
        
        // 1. 转换（中缀）表达式为逆波兰式
        HashMap op = new HashMap<>();
        ArrayList postfix = new ArrayList<>();
        ArrayDeque stack = new ArrayDeque<>();
        op.put("+", 1);
        op.put("-", 1);
        op.put("*", 2);
        op.put("/", 2);
        op.put("(", 3);
        op.put(")", 3);
        
        for (String token : expression) {
            if (!op.containsKey(token)) {
                postfix.add(token);
                continue;
            }
            if (!stack.isEmpty()) {
                if (token.equals(")")) {
                    while (!stack.isEmpty()) {
                        if (stack.peek().equals("(")) {
                            stack.pop();
                            break;
                        }
                        postfix.add(stack.pop());
                    }
                } else if (op.get(stack.peek()) >= op.get(token)) {
                    while (!stack.isEmpty() && op.get(stack.peek()) >= op.get(token)) {
                        if (stack.peek().equals("(")) {
                            break;
                        }
                        postfix.add(stack.pop());
                    }
                    stack.push(token);
                } else {
                    stack.push(token);
                }
            } else {
                stack.push(token);
            }
        }

        while (!stack.isEmpty()) {
            postfix.add(stack.pop());
        }
        
        // 鲁棒性检测，表达式中没有操作数
        if (postfix.isEmpty()) {
            return result;
        }
        
        // 2. 计算逆波兰式值
        ArrayDeque stack1 = new ArrayDeque<>();
        for (String token : postfix) {
            if (!op.containsKey(token)) {
                stack1.push(Integer.parseInt(token));
                continue;
            }
            int first = stack1.pop();
            int second = stack1.pop();
            if (token.equals("+")) {
                stack1.push(second + first);
            } else if (token.equals("-")) {
                stack1.push(second - first);
            } else if (token.equals("*")) {
                stack1.push(second * first);
            } else {
                stack1.push(second / first);
            }
        }
        result = stack1.pop();
        return result;
    }
}

参考

[1] http://blog.csdn.net/antineutrino/article/details/6763722/

服务器托管私有云 javascript算法题字符串算法题最难的算法题 java有趣算法题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69965.html

JS知识 - 收藏集 - 掘金

摘要：攻击中文名称跨站请求伪造，也被称为前端跨域问题及解决方案前端掘金同源策略同源策略限制从一个源加载的文档或脚本如何与来自另一个源的资源进行交互。二叉搜索树是二的数据结构与算法三集合前端掘金集合集合是由一组无序且唯一的项组成的。你真的懂 JavaScript 的正则吗？ - 掘金本文内容主要出处为《JavaScript权威指南》(第六版)，笔者只是在搬砖的同时整理思路，有误望及时指出，感...

UCloud 2019-08-20 17:30 评论0 收藏0
2018.11.19秋招末第二波前端实习/校招小结

摘要：背景个人背景就读于东北某普通二本院校计算机软件工程专业，现大四，北京实习前端方向，自学，技术栈时间背景大概是在月日准备好简历开始投递秋招差不多已经结束招聘岗位不多，投递对象为大一些的互联网公司事件背景第一个入职的是好未来的前端实习岗，待遇工背景个人背景就读于东北某普通二本院校计算机软件工程专业，现大四，北京实习前端方向，自学，vue技术栈时间背景大概是在11月9日准备...

suxier 2019-08-29 17:21 评论0 收藏0
2018.11.19秋招末第二波前端实习/校招小结

摘要：背景个人背景就读于东北某普通二本院校计算机软件工程专业，现大四，北京实习前端方向，自学，技术栈时间背景大概是在月日准备好简历开始投递秋招差不多已经结束招聘岗位不多，投递对象为大一些的互联网公司事件背景第一个入职的是好未来的前端实习岗，待遇工背景个人背景就读于东北某普通二本院校计算机软件工程专业，现大四，北京实习前端方向，自学，vue技术栈时间背景大概是在11月9日准备...

canger 2019-08-26 13:25 评论0 收藏0
7月份前端资源分享

摘要：更多资源请文章转自月份前端资源分享的作用数组元素随机化排序算法实现学习笔记数组随机排序个变态题解析上个变态题解析下中的数字前端开发笔记本过目不忘正则表达式聊一聊前端存储那些事儿一键分享到各种写给刚入门的前端工程师的前后端交互指南物联网世界的更多资源请Star：https://github.com/maidishike... 文章转自：https://github.com/jsfr...

pingan8787 2019-08-20 17:53 评论0 收藏0