Evaluate the value of an arithmetic expression in .
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
思路：stack的经典题目，遇到数字压栈，遇到符号出栈两个计算再入栈。
import java.util.Stack;public class Solution { public int evalRPN(String[] tokens) { Stack stack = new Stack (); int a, b; for (int i = 0; i < tokens.length; i++) { if (tokens[i].equals("+")) { a = stack.pop(); b = stack.pop(); stack.push(b + a); } else if (tokens[i].equals("-")) { a = stack.pop(); b = stack.pop(); stack.push(b - a); } else if (tokens[i].equals("*")) { a = stack.pop(); b = stack.pop(); stack.push(b * a); } else if (tokens[i].equals("/")) { a = stack.pop(); b = stack.pop(); stack.push(b / a); } else { stack.push(Integer.parseInt(tokens[i])); } } return stack.pop(); } public static void main(String[] args) { System.out.println(new Solution().evalRPN(new String[] { "2", "1", "+", "3", "*" })); System.out.println(new Solution().evalRPN(new String[] { "4", "13", "5", "/", "+" })); }}
第二遍记录：
注意对于减法和除法，先pop出来的被减数和被除数，后pop出来的是减数和除数。
扩展：
根据中序表达式生成逆波兰表示法。
第三遍记录： 实现了扩展， 中序表达式 =》逆波兰表达式，基本可以实现一个计算器的功能，支持(),+,-,*,/，并且可以扩展。
转换思路：遍历中序表达式，对于当前字符
如果是‘(’，直接压栈；
如果是')'，pop 栈内元素到输出中，直到遇到‘(’。
如果是0-9，直接输出。
如果是操作符（+-*/等），压栈之前把栈顶优先级大于等于自己的全部pop到输出 然后压栈自己。
最后将栈内剩余元素pop到输出中。
import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Stack;public class Solution { public int calcu(String exp) { return evalRPN(generateRPN(exp)); } public int evalRPN(String[] tokens) { Stack stack = new Stack (); int a, b; for (int i = 0; i < tokens.length; i++) { if (tokens[i].equals("+")) { a = stack.pop(); b = stack.pop(); stack.push(b + a); } else if (tokens[i].equals("-")) { a = stack.pop(); b = stack.pop(); stack.push(b - a); } else if (tokens[i].equals("*")) { a = stack.pop(); b = stack.pop(); stack.push(b * a); } else if (tokens[i].equals("/")) { a = stack.pop(); b = stack.pop(); stack.push(b / a); } else { stack.push(Integer.parseInt(tokens[i])); } } return stack.pop(); } /** * convert inorder expression to rerverse polish notation * * @param inorder * @return */ public String[] generateRPN(String inorder) { System.out.println("inorder:" + inorder); int n = inorder.length(); Stack stack = new Stack (); HashMap pri = new HashMap (); config(pri); List res = new ArrayList (); for (int i = 0; i < n; i++) { char ch = inorder.charAt(i); if (Character.isSpaceChar(ch)) continue; if (ch == '(') { // for '(' stack.push('('); } else if (ch == ')') { // for ')' char out = 0; while ((out = stack.pop()) != '(') { res.add(out + ""); } } else if (ch >= '0' && ch < '9') { // for operand res.add(ch + ""); } else { // for operator if (stack.isEmpty() || pri.get(ch) > pri.get(stack.peek())) { stack.push(ch); } else { while (!stack.isEmpty() && pri.get(ch) <= pri.get(stack.peek())) { res.add(stack.pop() + ""); } // don't forget this stack.push(ch); } } } // don't forget this while (!stack.isEmpty()) { res.add(stack.pop() + ""); } String[] ret = new String[res.size()]; res.toArray(ret); System.out.println("RPN:" + Arrays.toString(ret)); return ret; } /** * config the priority * * @param map */ private void config(HashMap map) { map.put('+', 1); map.put('-', 1); map.put('*', 2); map.put('/', 2); map.put('(', Integer.MIN_VALUE); } public static void main(String[] args) { System.out.println(new Solution().calcu("((2 + 1) * 3)")); System.out.println(new Solution().calcu("(4 + (3 / 5))")); System.out.println(new Solution().calcu("(1+2+3)")); System.out.println(new Solution().calcu("1+2*3+(4*5+6)*7")); System.out.println(new Solution().calcu("1+2*3")); System.out.println(new Solution().calcu("1*2+3")); System.out.println(new Solution().calcu("(1+2)*3")); }}