美文网首页
LeetCode-150- 逆波兰表达式求值

LeetCode-150- 逆波兰表达式求值

作者: 醉舞经阁半卷书 | 来源:发表于2022-01-24 10:03 被阅读0次

    逆波兰表达式求值

    题目描述:根据 逆波兰表示法,求表达式的值。

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

    说明:

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

    逆波兰表达式:详情介绍见逆波兰表达式

    示例说明请见LeetCode官网。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    解法一:栈

    利用栈后进先出的特点来求解逆波兰表达式(后缀表达式)的值,具体求解过程如下:

    • 如果原表达式只有一个参数,则直接返回操作数。
    • 否则,声明一个操作数栈nums用来存放操作数,按顺序遍历逆波兰表达式的字符:
      • 如果当前字符是操作数,则直接入栈;
      • 如果当前字符是操作符,则从栈中取出2个操作数,并按照当前操作符进行计算,将计算结果重新计算。
    • 最后,返回操作数栈的唯一的一个值,即为逆波兰表达式的求值结果。
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public class LeetCode_150 {
    
        public static int evalRPN(String[] tokens) {
            if (tokens.length == 1) {
                return Integer.valueOf(tokens[0]);
            }
            List<String> operatorList = new ArrayList<>();
            operatorList.add("+");
            operatorList.add("-");
            operatorList.add("*");
            operatorList.add("/");
    
            // 操作数栈
            Stack<Integer> nums = new Stack<>();
    
            for (int i = 0; i < tokens.length; i++) {
                if (operatorList.contains(tokens[i])) {
                    // 如果是操作符,取出2个操作数进行运算然后将结果重新入栈
                    int num1 = Integer.valueOf(nums.pop());
                    int num2 = Integer.valueOf(nums.pop());
                    if ("+".equals(tokens[i])) {
                        nums.push(num2 + num1);
                    } else if ("-".equals(tokens[i])) {
                        nums.push(num2 - num1);
                    } else if ("*".equals(tokens[i])) {
                        nums.push(num2 * num1);
                    } else if ("/".equals(tokens[i])) {
                        nums.push(num2 / num1);
                    }
                } else {
                    // 如果是操作数,则入栈
                    nums.push(Integer.valueOf(tokens[i]));
                }
            }
            return nums.pop();
        }
    
        public static void main(String[] args) {
            // 测试用例
            String[] tokens = new String[]{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
            // 转换成中缀表达式的结果是: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
            // 计算结果为: 22
            System.out.println(evalRPN(tokens));
        }
    }
    

    【每日寄语】 世上无难事,只要肯登攀。

    相关文章

      网友评论

          本文标题:LeetCode-150- 逆波兰表达式求值

          本文链接:https://www.haomeiwen.com/subject/qpcbhrtx.html