进阶:空间复杂度 , 时间复杂度
["20", "10", "+", "30", "*"] -> ((20 + 10) * 30) -> 900 ["40", "130", "50", "/", "+"] -> (40 + (130 / 50)) -> 42
["20", "10", "+", "30", "*"] -> ((20 + 10) * 30) -> 900 ["40", "130", "50", "/", "+"] -> (40 + (130 / 50)) -> 42
["20","10","+","30","*"]
900
["20"]
20
import java.util.*; public class Solution { /** * * @param tokens string字符串一维数组 * @return int整型 */ public int evalRPN (String[] tokens) { Stack<String> stack = new Stack<>(); for (int i = tokens.length-1; i >=0; i--) { String token = tokens[i]; doStackPush(token,stack); } return Integer.parseInt(stack.pop()); } public void doStackPush(String token,Stack<String>stack) { if (stack.size()==0) { stack.push(token); return; } // token 是运算符 if (!isNum(token)) { stack.push(token); } else { // token 是数字 if (!isNum(stack.peek())) { stack.push(token); } else { String num1 = token; String num2 = stack.pop(); String op = stack.pop(); String val = String.valueOf(calaulate(num1, op, num2)); if (stack.size()>0 && isNum(stack.peek())) { doStackPush(val,stack); } else { stack.push(val); } } } } public boolean isNum(String str) { if (!str.equals("+") && !str.equals("-") && !str.equals("*") && !str.equals("/")) return true; return false; } public int calaulate(String num1,String op,String num2) { int n1 = Integer.parseInt(num1); int n2 = Integer.parseInt(num2); switch (op) { case "+": return n1+n2; case "-": return n1-n2; case "*": return n1*n2; case "/": return n1/n2; } return -1; } }
import java.util.*; public class Solution { /** * * @param tokens string字符串一维数组 * @return int整型 */ public int evalRPN (String[] tokens) { Stack<Integer> stack = new Stack<>(); for(String s : tokens) { if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) { int b = stack.pop(); int a = stack.pop(); switch(s) { case "+":stack.push(a + b);break; case "-":stack.push(a - b);break; case "*":stack.push(a * b);break; case "/":stack.push(a / b);break; } }else { stack.push(Integer.valueOf(s)); } } return stack.pop(); } }
import java.util.*; public class Solution { /** * * @param tokens string字符串一维数组 * @return int整型 */ public int evalRPN (String[] tokens) { Stack<Integer> stack = new Stack<>(); for (String s: tokens){ int a = 0; int b = 0; switch (s){ case "+": a = stack.pop(); b = stack.pop(); stack.push(a+b); break; case "-": a = stack.pop(); b = stack.pop(); stack.push(b-a); break; case "*": a = stack.pop(); b = stack.pop(); stack.push(a*b); break; case "/": a = stack.pop(); b = stack.pop(); stack.push(b/a); break; default: stack.push(Integer.parseInt(s)); } } return stack.pop(); } }
public int evalRPN (String[] tokens) { // write code here if(tokens == null || tokens.length == 0){ return 0; } ArrayList<String> sign = new ArrayList<String>(){{ add("+"); add("-"); add("*"); add("/"); }}; Stack<String> stack = new Stack<>(); for(String ele : tokens){ if(!sign.contains(ele)){ stack.push(ele); }else { int res = 0; int num2 = Integer.parseInt(stack.pop()); int num1 = Integer.parseInt(stack.pop()); if(ele.equals("+")){ res = num1 + num2; }else if(ele.equals("-")){ res = num1 - num2; }else if(ele.equals("*")){ res = num1 * num2; }else if(ele.equals("/")){ res = num1 /num2; }else { res = 0; } stack.push("" + res); } } return Integer.parseInt(stack.pop()); }
public int evalRPN (String[] tokens) { // write code here if(tokens.length == 0){ return 0; } HashSet<String> hashSet = new HashSet<>(); hashSet.add("+"); hashSet.add("-"); hashSet.add("/"); hashSet.add("*"); Stack<Integer> stack = new Stack<>(); for(String s : tokens){ if(!hashSet.contains(s)){ stack.push(Integer.parseInt(s)); }else { int second = stack.pop(); int first = stack.pop(); int temp = 0; switch (s){ case "+": temp = first + second; stack.push(temp); break; case "-": temp = first - second; stack.push(temp); break; case "*": temp = first * second; stack.push(temp); break; default: temp = first / second; stack.push(temp); } } } return stack.peek(); }做法都差不多,只不过是用了一个hashSet来辅助判断
import java.util.Stack; public class Solution { public int evalRPN(String[] tokens) { int i=0,n,a,b,t=0; n=tokens.length; if(n==1) return Integer.parseInt(tokens[0]); Stack<String> stack=new Stack<String>(); stack.push(tokens[i++]); stack.push(tokens[i++]); stack.push(tokens[i++]); while(!stack.isEmpty()){ if(stack.peek().equals("+")){ stack.pop(); b=Integer.parseInt(stack.peek()); stack.pop(); a=Integer.parseInt(stack.peek()); stack.pop(); t=a+b; stack.push(Integer.toString(t)); } else if(stack.peek().equals("-")){ stack.pop(); b=Integer.parseInt(stack.peek()); stack.pop(); a=Integer.parseInt(stack.peek()); stack.pop(); t=a-b; stack.push(Integer.toString(t)); } else if(stack.peek().equals("*")){ stack.pop(); b=Integer.parseInt(stack.peek()); stack.pop(); a=Integer.parseInt(stack.peek()); stack.pop(); t=a*b; stack.push(Integer.toString(t)); } else if(stack.peek().equals("/")){ stack.pop(); b=Integer.parseInt(stack.peek()); stack.pop(); a=Integer.parseInt(stack.peek()); stack.pop(); t=a/b; stack.push(Integer.toString(t)); } if(i<n) stack.push(tokens[i++]); else{ t=Integer.parseInt(stack.peek()); stack.pop(); } } return t; } }
import java.util.*; public class Solution { static int evalRPN(String[] tokens) { Deque<Integer> nums = new LinkedList<>(); //操作数栈 //如果是操作数就入栈,如果是操作符,就弹出栈,后弹出的是第一操作数 for (String token : tokens) { if (token.equals("+")||token.equals("-")||token.equals("*")||token.equals("/")){ int num1=0 , num2=1; if (!nums.isEmpty()) num2 = nums.pollFirst(); if (!nums.isEmpty()) num1 = nums.pollFirst(); switch (token) { case "+": nums.addFirst(num1 + num2); break; case "-": nums.addFirst(num1 - num2); break; case "*": nums.addFirst(num1 * num2); break; case "/": nums.addFirst(num1 / num2); break; } } else { nums.addFirst(Integer.parseInt(token)); } } return nums.isEmpty() ? 0 : nums.pollFirst(); } }
package leetcode; import java.util.Stack; /** * @ClassName EvalRPN * @Description * 计算逆波兰式(后缀表达式)的值 * 运算符仅包含“ +”,“ - ”,“*”和“/”,***作数可能是整数或其他表达式 * 例如: * [“2”,“1”,“+”,“3”,“*”] - >((2 + 1)* 3) - >9↵[“4”,“13”,“5”,“ /“,”+“] - >(4 +(13/5)) - > 6 * 在反向波兰表示法中计算算术表达式的值 。 * 有效的运算符是+, - ,*,/。每个操作数可以是整数或另一个表达式。 * * 一些例子: * * [“2”,“1”,“+”,“3”,“*”] - >((2 + 1)* 3) - >9↵[“4”,“13”,“5”,“ /“,”+“] - >(4 +(13/5)) - > 6 * @Author Wlison * @Date 2019/8/26 20:36 * @Version 1.0 **/ public class EvalRPN { //test public static void main(String[] args) { String[] str = {"4", "13", "5", "/", "+"}; System.out.println(new EvalRPN().evalRPN(str)); } public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); String opt = "+-*/"; for (int i = 0; i < tokens.length; i++) { if(!opt.contains(tokens[i])){ stack.push(Integer.valueOf(tokens[i])); }else{ int b = Integer.valueOf(stack.pop()); int a = Integer.valueOf(stack.pop()); int operate = getOperate(a, b, opt.indexOf(tokens[i])); stack.push(operate); } } return stack.pop(); } public int getOperate(int a,int b,int opt){ switch (opt){ case 0:return a+b; case 1:return a-b; case 2:return a*b; case 3:return a/b; default:return 0; } } }
public class Solution { public int evalRPN(String[] tokens) { // 定义一个空栈 // 从头至尾遍历字符串,只要没遍历完,用while循环 // 只要取到的字符是数字,就入栈 // 如果不是数字,就从栈中取出两个数字,和这个符号运算,得出的结果放回栈中。 // 遍历完所有的字符后,栈中一定还剩一个数字,取出来,即是结果。 int[] stack = new int[tokens.length]; String temp = ""; int k = 0; for(int i=0; i<tokens.length; i++){ temp = tokens[i]; if(temp.equals("+") || temp.equals("-") || temp.equals("*") || temp.equals("/")){ int num1 = stack[k-2]; int num2 = stack[k-1]; if(temp.equals("+")){ stack[k-2] = num1 + num2; }else if(temp.equals("-")){ stack[k-2] = num1 - num2; }else if( temp.equals("*") ){ stack[k-2] = num1 * num2; }else { stack[k-2] = num1 / num2; } k = k-1; }else{ int num = Integer.parseInt(tokens[i]); stack[k++] = num; } } return stack[0]; } }
看到用异常的大佬,好牛逼啊
public static int evalRPN(String[] tokens) { if (tokens == null){ return 0; } Stack<String> stack = new Stack<>(); int a = 0; int b = 0; for (int i = 0; i < tokens.length; i++) { switch (tokens[i]){ case "+": a = Integer.parseInt(stack.pop()); b = Integer.parseInt(stack.pop()); stack.push(String.valueOf(b + a)); break; case "-": a = Integer.parseInt(stack.pop()); b = Integer.parseInt(stack.pop()); stack.push(String.valueOf(b - a)); break; case "*": a = Integer.parseInt(stack.pop()); b = Integer.parseInt(stack.pop()); stack.push(String.valueOf(b * a)); break; case "/": a = Integer.parseInt(stack.pop()); b = Integer.parseInt(stack.pop()); stack.push(String.valueOf(b / a)); break; default: stack.push(tokens[i]); break; } } return Integer.parseInt(stack.pop()); }
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are+,-,*,/. Each operand may be an integer or another expression.
Some examples:
这一题提示信息是用栈来实现,那么思路为:如果当前元素是数字就入栈,否则就是运算符,那么就将这个运算符前面两个数字进行相应操作,并且将这个操作结果重新再放入栈中,参与下一次的运算。
import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
int res = 0;
if(tokens == null || tokens.length <= 0){
return res;
}
if(tokens.length == 1){
res = Integer.valueOf(tokens[0]);
}
for(String str:tokens){
if(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")){
int v1 = stack.pop();
int v2 = stack.pop();
if(str.equals("+")){
res = v1+v2;
}else if(str.equals("-")){
res = v2-v1;
}else if(str.equals("*")){
res = v1*v2;
}else if(str.equals("/")){
res = v2/v1;
}
stack.push(res);
}else{
stack.push(Integer.valueOf(str));
}
}
return res;
}
}
import java.util.Stack; public class Solution { public int evalRPN(String[] tokens) { int res = 0; if (tokens == null || tokens.length == 0) return res; int len = tokens.length; Stack<Integer> stack = new Stack(); int i = 0; for (; i < len; i++) { if (isNum(tokens[i])) stack.push(Integer.parseInt(tokens[i])); else { int a = stack.pop(); int b = stack.pop(); //除法有顺序要求哦 stack.push(operator(b, a, tokens[i])); } } if (i == len) return stack.pop(); return res; } private boolean isNum(String str) { boolean b = false; try { Integer.parseInt(str); b = true; } catch (Exception e) { } return b; } private int operator(int a, int b, String s) { int res = 0; switch (s) { case "+": { res = a + b; break; } case "-": { res = a - b; break; } case "*": { res = a * b; break; } case "/": { res = a / b; break; } } return res; } }
有两个表达式
(4 + (13 / 5)) = 6 (a)
((2 + 1) * 3) = 9 (b)
对应的两个表达式树(a)(b)
特点:数字都在叶子节点,运算符都在根节点。
. + *
/ \ / \
4 / + 3
/ \ / \
13 5 2 1
(a) (b)
来看一下表达式树的前中后三种顺序遍历结果;
中序:
4 + 13 / 5 --- (a)
2 + 1 * 3 --- (b)
可以看出,表达式树的中序遍历结果就是正常书写顺序,也是计算机可以直接求解的方式。
后序:
4 13 5 / + --- (a)
2 1 + 3 * --- (b)
此时遍历结果非书写顺序,计算机也不能直接求解,非要按照这个顺序用计算机求解,怎么办?
解决方案:栈
按照遍历顺序对元素如下的操作:
1、如果元素是数字,入栈
2、如果元素是操作符不入栈,反而弹栈两个元素a,b;将a作为运算符的左操作数,b作为右操作数计算得到结果c;将结果c入栈。
3、重复上述操作,直到没有元素时,此时栈中一定只有一个元素,将其返回。
前序:
+ 4 / 13 5 --- (a)
* + 2 / 3 --- (b)
此时遍历结果非书写顺序,计算机也不能直接求解,非要按照这个顺序用计算机求解,怎么办?
解决方案:栈
与后序列操作类似,只不过按照遍历顺序的逆序,为什么是这样呢?
因为:栈的特点可以暂存之前遇到的信息,在后续操作中可以从栈中取出之前保存的信息;
四则运算符都是二元运算符,因此一次计算的顺利完成需要3个信息,两数字,一运算符;
因此遇到数字时候压栈,遇到操作符时候不压栈,而弹出两个元素进行计算,这是合理的。
而观察表达式树我们发现,叶子节点全都是数字,跟节点全都是操作符号,在进一步可以这么想,父节点都是操作符,孩子节点都是数字(当然直观来看不是这样的,如表达式树(a)中根节点“+”的右孩子明明是“/”;其实在根节点“+”真正计算的时候,13 和 5的父节点“/”早就是新的数字了);结合树的遍历特点,要么遍历完孩子节点才遍历根节点(后序),要么遍历完孩子节点才遍历根节点(前序),总之,孩子节点(数字)总在父节点(符号)的一侧。不管是先序还是后序,我们都统一为先处理孩子节点,再处理父节点,后序顺序中,孩子节点刚好在父节点之前,因此不做顺序调整,而先序遍历的时候,孩子节点均在父节点之后,因此需要逆序调整。
思路:申请一个整数栈,遍历数组,遇到整数时将其亚入栈,遇到操作符数,从栈中弹出两个操作数进行计算,将就算结果压回栈中;如此反复,最后栈中的数字便是结算的结果
public int evalRPN(String[] tokens) {
Stack<Integer> numStack=new Stack<>();
String temp;
for(int i=0;i<tokens.length;i++){
temp=tokens[i];
if(temp.equals("+") || temp.equals("-") || temp.equals("*") || temp.equals("/") ){
if(numStack.size()<2)
return -1;
else{
int num2=numStack.pop();
int num1=numStack.pop();
switch (temp){
case "+":
numStack.push(num1+num2);break;
case "-":
numStack.push(num1-num2);break;
case "*":
numStack.push(num1*num2);break;
case "/":
numStack.push(num1/num2);break;
default:
return -1;
}
}
}else if(isNum(temp)){
numStack.push(Integer.parseInt(temp));
}else
return -1;
}
if(numStack.size()!=1)
return -1;
else
return numStack.pop();
}
private boolean isNum(String str){ //判断是否为数字,可以为负数
for(int i=0;i<str.length();i++){
if ((str.charAt(i)<'0' || str.charAt(i)>'9') && !(i==0 && str.charAt(0)=='-'))
return false;
}
return true;
}