表达式类算法题小结
[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/