Leetcode刷题100天—_150_逆波兰表达式求值(栈)—day04

左手的ㄟ右手 2022-09-05 12:56 100阅读 0赞

前言：

> 作者：神的孩子在歌唱  
> 大家好，我叫运智

![image-20210816221624245][]

根据 **逆波兰表示法**，求表达式的值。

有效的算符包括 `+`、`-`、`*`、`/` 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

**说明：**

*  整数除法只保留整数部分。
 *  给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

**示例 1：**

输入：tokens = ["2","1","+","3","*"]
    输出：9
    解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

**示例 2：**

输入：tokens = ["4","13","5","/","+"]
    输出：6
    解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

**示例 3：**

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
    输出：22
    解释：
    该算式转化为常见的中缀算术表达式为：
      ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
    = ((10 * (6 / (12 * -11))) + 17) + 5
    = ((10 * (6 / -132)) + 17) + 5
    = ((10 * 0) + 17) + 5
    = (0 + 17) + 5
    = 17 + 5
    = 22

**提示**：

*  `1 <= tokens.length <= 104`
 *  `tokens[i]` 要么是一个算符（"`+`"、"`-`"、"`*`" 或 “`/`”），要么是一个在范围 `[-200, 200]` 内的整数

**逆波兰表达式**：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

*  平常使用的算式则是一种中缀表达式，如 **( 1 + 2 ) \* ( 3 + 4 )** 。
 *  该算式的逆波兰表达式写法为 **( ( 1 2 + ) ( 3 4 + ) \* )** 。

逆波兰表达式主要有以下两个优点：

*  去掉括号后表达式无歧义，上式即便写成 `1 2 + 3 4 + *` 也可以依据次序计算出正确结果。
 *  适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

> 来源：力扣（LeetCode）
> 
> 链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
> 
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 代码 ###

package 栈;
    
    import java.util.Deque;
    import java.util.HashMap;
    import java.util.Stack;
    
    /* * 3 * https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/ */
    public class _150_逆波兰表达式求值 { 
    	 public int evalRPN(String[] tokens) { 
    // 创建一个空栈
    		 	Stack<Integer> stack=new Stack<>();
    // int len=;
    			
    		 	for(int i =0;i<tokens.length;i++) { 
    		 		String token=tokens[i];
    		 		if (!("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token))) { 
    // 解析为整数
    		 			stack.push(Integer.parseInt(token));
    		 		}
    // 如果碰上操作符
    		 		else { 
    // 出栈两个数
    		 			int num2=stack.pop();
    		 			int num1=stack.pop();
    // 通过switch判断用什么
    		 			switch(token) { 
    		 			case "+":
    		 				stack.push(num1+num2);
    		 				break;
    		 			case "-":
    		 				stack.push(num1-num2);
    		 				break;
    		 			case "*":
    		 				stack.push(num1*num2);
    		 				break;
    		 			case "/":
    		 				stack.push(num1/num2);
    		 				break;
    		 			default:
    		 			}
    		 		}
    		 	}
    		 	return stack.pop();	
    	    }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114  
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210816221624245]: /images/20220829/fd21551771ee47c5a0e11f2fa24d6cc0.png