当前位置：首页 > news >正文

关于力扣150题目——逆波兰表达式求值Java实现的三种解法

news 来源：原创 2024/9/20 21:41:46

题目介绍

逆波兰表达式是一种后缀表达式，其运算符位于操作数之后。力扣150题目要求我们实现一个函数，计算给定逆波兰表达式的值。本文将介绍三种不同的Java实现方法来解决这个问题。

解法一：使用栈

这是最直观和常见的解法，使用栈来存储操作数，并在遇到运算符时从栈中弹出操作数进行计算，然后将结果压入栈中。以下是具体实现：

import java.util.*;public class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String token : tokens) {if (token.equals("+")) {int num2 = stack.pop();int num1 = stack.pop();stack.push(num1 + num2);} else if (token.equals("-")) {int num2 = stack.pop();int num1 = stack.pop();stack.push(num1 - num2);} else if (token.equals("*")) {int num2 = stack.pop();int num1 = stack.pop();stack.push(num1 * num2);} else if (token.equals("/")) {int num2 = stack.pop();int num1 = stack.pop();stack.push(num1 / num2);} else {stack.push(Integer.parseInt(token));}}return stack.pop();}
}

解法二：使用数组模拟栈

由于逆波兰表达式求值只需要后进先出的特性，我们也可以使用数组来模拟栈的操作，从而避免使用Java的Stack类。这种方法可以稍微提高一点性能，因为省去了Stack类的一些操作开销。以下是实现代码：

public class Solution {public int evalRPN(String[] tokens) {int[] stack = new int[tokens.length];int index = 0;for (String token : tokens) {switch (token) {case "+":stack[index - 2] += stack[--index];break;case "-":stack[index - 2] -= stack[--index];break;case "*":stack[index - 2] *= stack[--index];break;case "/":stack[index - 2] /= stack[--index];break;default:stack[index++] = Integer.parseInt(token);break;}}return stack[0];}
}

解法三：使用递归和指针

这种解法使用递归来实现逆波兰表达式的求值，通过一个指针来遍历表达式数组，每次递归处理一个运算符或操作数，直至整个表达式求值完成。以下是实现代码：

public class Solution {int index = 0;public int evalRPN(String[] tokens) {index = tokens.length - 1;return eval(tokens);}private int eval(String[] tokens) {String token = tokens[index--];if (token.equals("+")) {return eval(tokens) + eval(tokens);} else if (token.equals("-")) {return eval(tokens) - eval(tokens);} else if (token.equals("*")) {return eval(tokens) * eval(tokens);} else if (token.equals("/")) {return eval(tokens) / eval(tokens);} else {return Integer.parseInt(token);}}
}