Leetcode148-LC2 后缀表达式求值

原创
10/16 02:02
阅读数 9

后缀表达式求值

题目描述

计算逆波兰式(后缀表达式)的值
运算符仅包含"+","-","*"和"/",被操作数可能是整数或其他表达式
例如:

["20", "10", "+", "30", "*"] -> ((20 + 10) * 30) -> 900
["40", "130", "50", "/", "+"] -> (40 + (130 / 50)) -> 42

思路


前缀、中缀、后缀表达式(逆波兰表达式)

参考:https://www.cnblogs.com/chensongxian/p/7059802.html

  • 中缀表达式:
    • 中缀表达式就是常见的运算表达式,如(3+4)×5-6
  • 前缀表达式:
    • 前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前
    • 比如:- × + 3 4 5 6
  • 后缀表达式:
    • 后缀表达式又称逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后
    • 比如:3 4 + 5 × 6 -

参考:https://www.nowcoder.com/questionTerminal/22f9d7dd89374b6c8289e44237c70447?f=discussion

这一题的考点有2个,

  1. 利用stack来计算波兰表达式的值,这都是套路
  2. 程序鲁棒性,考虑各种可能的异常

思路

  • 1.遇到操作数就出栈,把计算结果入栈
    • 1.1计算结果时,stack至少2个数,否则不合法,返回0
  • 2.遇到数字就入栈
    • 2.1如果不是操作数,也无法转换为数字,就返回0,这里用try catch
  • 3.结果要合法:
    • 3.1如果遍历完成,stack的元素不止1个,说明不合法,返回0
    • 3.2当stack元素只有一个的时候,返回结果
package leetcode148.lc2;

import java.util.*;

public class Solution01 {
    /**
     *
     * @param tokens string字符串一维数组
     * @return int整型
     */
    public int evalRPN (String[] tokens) {
        if (tokens == null || tokens.length == 0) return 0;
        Stack<Integer> s = new Stack<Integer>();
        for (int i = 0; i < tokens.length; i++) {
            String cur = tokens[i];

            if (cur.equals("+") || cur.equals("-") || cur.equals("*") || cur.equals("/")) {
                if (s.size() < 2) return 0; // 如果操作数不合法,没有足够的数来操作,返回0

                int after = s.pop();
                int before = s.pop();

                if (cur.equals("+")) {
                    s.push(before + after);
                } else if (cur.equals("-")) {
                    s.push(before - after);
                } else if (cur.equals("*")) {
                    s.push(before * after);
                } else if (cur.equals("/")) {
                    s.push(before / after);
                }
            } else { // 不是操作符
                try {
                    int num = Integer.parseInt(cur);
                    s.push(num);
                } catch (NumberFormatException e) {
                    return 0; // 非法字符返回0
                }
            }
        }

        return s.size() == 1 ? s.pop() : 0; // 最后栈中只有一个结果数值,其他情况为异常
    }
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部