给定一个逆波兰表达式，求表达式的值。
数据范围：表达式长度满足 
，表达式中仅包含数字和 + ，- , * , / ，其中数字的大小满足 
。
[编程题]逆波兰表达式求值
核心逻辑，遇到数字就进栈，遇到符号就从栈内弹出两个数字，第一个弹出的为操作数2，第二个弹出的为操作数1，运算后将结果入栈。
正常情况下，最后的栈内应该只有一个元素，这个元素就是最终结果，其余情况下都是输入错误，应该捕获异常并返回错误提示（代码省略）。
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param tokens string字符串一维数组
* @return int整型
*/
public static int evalRPN(String[] tokens) {
// write code here
Deque<String> stack = new ArrayDeque<>();
for (String str : tokens) {
if ("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)) {
Integer optionNum2 = Integer.parseInt(stack.pop());
Integer optionNum1 = Integer.parseInt(stack.pop());
switch (str) {
case "+":
stack.push(String.valueOf(optionNum1 + optionNum2));
break;
case "-":
stack.push(String.valueOf(optionNum1 - optionNum2));
break;
case "*":
stack.push(String.valueOf(optionNum1 * optionNum2));
break;
case "/":
stack.push(String.valueOf(optionNum1 / optionNum2));
}
} else {
stack.push(str);
}
}
return Integer.parseInt(stack.pop());
}
编辑于 2024-03-28 14:18:12
回复(0)
java
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param tokens string字符串一维数组
* @return int整型
*/
public int evalRPN (String[] tokens) {
// write code here
Stack<Integer> stack = new Stack<>();
// int res= 0;
for(String token : tokens){
if(token.matches("-?[0-9]+")){
stack.push(Integer.valueOf(token));
}else{
Integer a = stack.pop();
Integer b = stack.pop();
int res = compute(b,a,token);
stack.push(res);
}
}
return stack.pop();
}
public static int compute(Integer a, Integer b, String token){
if(token.equals("+")){
return a+b;
} else if(token.equals("-")){
return a-b;
} else if(token.equals("*")){
return a*b;
}
return a/b;
}
}
发表于 2022-11-09 17:41:15
回复(0)
后缀表达式思路:准备一个栈，循环向栈中加入元素，判断当前元素是符号还是数字，如果是符号，就取出栈中最上面的两个元素，也就是pop()两次，将这两个数与当前的符号进行运算，需要注意的是如果是"-"或者"/",则需要用第二次取出来的元素减去第一次的元素，除也是同理。
我这里主要是利用了一种异常处理机制来判断当前元素是符号还是数字，比较方便
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param tokens string字符串一维数组
* @return int整型
*/
public int evalRPN (ArrayList tokens) {
// write code here
Stack<String> stack = new Stack<>();
for (int i = 0; i < tokens.size(); i++) {
if (judgeIsNum((String)tokens.get(i))) {
stack.push((String)tokens.get(i));
} else {
//取出栈顶的两个元素与当前运算符进行计算
int a = Integer.parseInt(stack.pop());
int b = Integer.parseInt(stack.pop());
int res = 0;
if ("+".equals((String)tokens.get(i)) )
res = a + b;
if ("-".equals((String)tokens.get(i)))
res = b - a;
if ("*".equals((String)tokens.get(i)))
res = a * b;
if ("/".equals((String)tokens.get(i)))
res = b / a;
//再将计算结果压入栈中
stack.push(String.valueOf(res));
}
}
return Integer.parseInt(stack.pop());
}
public boolean judgeIsNum(String s) {
try {
Integer.parseInt(s);
} catch (Exception e) {
return false;
}
return true;
}
}
发表于 2022-10-05 21:17:56
回复(0)
public class Solution {
public int evalRPN (String[] tokens) {
int a;
int b;
int result;
Stack stack = new Stack();
for(int i=0;i<tokens.length;i++) {
switch(tokens[i]) {
case "+":
a=stack.pop();
b=stack.pop();
result=b+a;
stack.push(result);
break;
case "-":
a=stack.pop();
b=stack.pop();
result=b-a;
stack.push(result);
break;
case "*":
a=stack.pop();
b=stack.pop();
result=b*a;
stack.push(result);
break;
case "/":
a=stack.pop();
b=stack.pop();
result=b/a;
stack.push(result);
break;
default:
stack.push(Integer.parseInt(tokens[i]));
}
}
return stack.top();
}
}
发表于 2022-07-02 21:48:54
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param tokens string字符串一维数组
* @return int整型
*/
public int evalRPN (String[] tokens) {
// write code here
Stack<Integer> stack = new Stack<Integer>();
Integer num1, num2 = 0;
for (String str : tokens) {
if (!"+".equals(str) && !"-".equals(str) && !"*".equals(str) &&
!"/".equals(str)) {
Integer newInt = Integer.valueOf(str);
stack.push(newInt);
} else {
switch (str) {
case "+":
num1 = stack.pop();
num2 = stack.pop();
stack.push(num2 + num1);
break;
case "-":
num1 = stack.pop();
num2 = stack.pop();
stack.push(num2 - num1);
break;
case "*":
num1 = stack.pop();
num2 = stack.pop();
stack.push(num2 * num1);
break;
case "/":
num1 = stack.pop();
num2 = stack.pop();
stack.push(num2 / num1);
break;
}
}
};
return stack.pop();
}
}
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param tokens string字符串一维数组
* @return int整型
*/
public int evalRPN (String[] tokens) {
// write code here
Stack<Integer> stack = new Stack<Integer>();
Integer num1, num2 = 0;
for (String str : tokens) {
if (!"+".equals(str) && !"-".equals(str) && !"*".equals(str) &&
!"/".equals(str)) {
Integer newInt = Integer.valueOf(str);
stack.push(newInt);
} else {
switch (str) {
case "+":
num1 = stack.pop();
num2 = stack.pop();
stack.push(num2 + num1);
break;
case "-":
num1 = stack.pop();
num2 = stack.pop();
stack.push(num2 - num1);
break;
case "*":
num1 = stack.pop();
num2 = stack.pop();
stack.push(num2 * num1);
break;
case "/":
num1 = stack.pop();
num2 = stack.pop();
stack.push(num2 / num1);
break;
}
}
};
return stack.pop();
}
}
发表于 2022-04-27 14:37:10
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param tokens string字符串一维数组
* @return int整型
*/
public int evalRPN (String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
if (!isOp(tokens[i])) {
stack.push(Integer.parseInt(tokens[i]));
} else {
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(doOp(num1,tokens[i],num2));
}
}
return stack.pop();
}
private boolean isOp(String str) {
if ("+".equals(str) ||
"-".equals(str) ||
"*".equals(str) ||
"/".equals(str)) return true;
return false;
}
private int doOp(int num1,String op,int num2) {
if ("+".equals(op)) return num1+num2;
else if ("-".equals(op)) return num1-num2;
else if ("*".equals(op)) return num1*num2;
else return num1/num2;
}
}
发表于 2022-04-01 15:25:23
回复(0)
只说一点 注意出栈的顺序a，b -> b operator a !
public int evalRPN (String[] tokens) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
for (String t : tokens) {
if (t.equals("+") || t.equals("-")
|| t.equals("*") || t.equals("/")) {
int a = stack.pop(), b = stack.pop();
if (t.equals("+")) stack.push(b+a);
else if (t.equals("-")) stack.push(b-a);
else if (t.equals("*")) stack.push(b*a);
else stack.push(b/a);
} else {
stack.push(Integer.parseInt(t));
}
}
return stack.peek();
}
发表于 2022-01-11 12:42:48
回复(0)
用计算逆波兰表达式的流程就行，遇到数字就压栈，遇到运算符就弹出栈顶两个数进行计算，然后把计算结果压入栈中，直到栈中只剩下最后一个数，就是整个逆波兰表达式的计算结果。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param tokens string字符串一维数组
* @return int整型
*/
public int evalRPN (String[] tokens) {
// write code here
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < tokens.length; i++) {
if(isDigit(tokens[i])){
stack.push(Integer.parseInt(tokens[i]));
}else{
if(tokens[i].equals("+")){
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(num1 + num2);
}else if(tokens[i].equals("-")){
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(num1 - num2);
}else if(tokens[i].equals("*")){
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(num1 * num2);
}else if(tokens[i].equals("/")){
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(num1 / num2);
}
}
}
return stack.pop();
}
private boolean isDigit(String s) {
try{
Integer.parseInt(s);
return true;
}catch(Exception e) {
return false;
}
}
}
发表于 2021-12-22 20:14:20
回复(0)
问题信息
难度：
10条回答
92收藏
4849浏览
通过挑战的用户
查看代码-
2022-10-24 22:29:14
-
2022-09-16 18:18:28
-
2022-09-16 18:07:58
-
2022-09-16 15:24:43 -
2022-09-16 14:07:13
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
