后缀表达式求值

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();
    }

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;
    }
}

刚开始想的是如何将字符串数组中的数字型字符串识别出来，然后利用栈判断。想到了正则表达式，然后写了个函数判断，最后***竟然不给过。然后修改弃用判定函数，直接switch四种符号之外的就默认为数字，然后就很好解开了

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;
    }