题目:
给你一个字符串数组 tokens
,表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
栈的典型例题。题目要求为:求后缀表达式值。
示例 1:
输入:tokens = ["2","1","+","3","*"] 输出:9 解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
示例 2:
输入:tokens = ["4","13","5","/","+"] 输出:6 解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
以示例1、2为例,将后缀表达式转换为中缀表达式
例1:遇到数字2 ,1放入栈中,遇到 + 则弹出前两个数字(顺序为1 ,2),将前两个数字进行相加后再放回栈中。然后遇到3放入栈中,遇到 * 将两个前两个数字(3 和 3)弹出相乘后,放入栈中。此时栈里只存放这个表达式的结果9
例2:遇到前三个数字放入栈中。遇到 / 后,将前两个数字依次弹出(顺序为5,13),第二个弹出的是被除数13,第一个是除数5。 将运算结果放入栈中,此时栈里为 元素为13/5 和 4 。最后遇到+ ,将前两个元素弹出,运算结果放入栈中。
需要注意的是,后弹出的数要在运算符的左边。如 13 5 /
代码设计:遍历字符数组, 如果字符数组中遍历数字,就push进栈中。如果遍历到四个运算符之一,则将栈弹出两次,然后将弹出的两个数operand1和operand2做运算,运算结果再push进栈里。
代码如下:
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String token : tokens){
if(token.equals("-")){
int operand1 = stack.pop();
int operand2 = stack.pop();
stack.push(operand2 - operand1); //后弹出的数作为被减数
}else if(token.equals("+")){
int operand1 = stack.pop();
int operand2 = stack.pop();
stack.push(operand2 + operand1);
}else if(token.equals("*")){
int operand1 = stack.pop();
int operand2 = stack.pop();
stack.push(operand2 * operand1);
}else if(token.equals("/")){
int operand1 = stack.pop();
int operand2 = stack.pop();
stack.push(operand2 / operand1);//后弹出的数作为被除数
}else{
//传入的是字符数组,需要将字符串转为int。
Integer number = Integer.parseInt(token);
stack.push(number);
}
}
return stack.peek(); //也可以是stack.pop();
}
}
标签:Java,Leetcode150,operand2,int,pop,求值,operand1,stack,表达式
From: https://blog.csdn.net/m0_73904503/article/details/139899643