专栏首页码字搬砖逆波兰表达式求值

逆波兰表达式求值

1.什么是逆波兰表达式? 也叫后缀表达式,(3+4)*5-6 对应的逆波兰表达式 3 4 + 5 * 6 -

2.代码

/**
 * @author shengjk1
 * @date 2020/2/16
 */
/*
逆波兰表达式
 */
public class PolandNotation {
	public static void main(String[] args) {
		//(3+4)*5-6
		String suffixExpression = "3 4 + 5 * 6 -";
		List<String> listString = getListString(suffixExpression);
		System.out.println(listString);
		System.out.println(calculate(listString));
		
	}
	
	//将逆波兰表达式转化为list
	public static List<String> getListString(String suffixExpression) {
		String[] split = suffixExpression.split(" ");
		ArrayList<String> list = new ArrayList<>();
		
		for (String s : split) {
			list.add(s);
		}
		return list;
	}
	
	/**
	 * 逆波兰表达式 求值
	 * <p>
	 * 从左至右扫描表达式,
	 * 遇到数字,将数字压入堆栈,
	 * 遇到运算符,弹出栈顶的两个数,
	 * 用运算符对它们做相应的计算(次栈顶元素和栈顶元素),并将结果入栈。
	 * 重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
	 *
	 * @param s
	 * @return
	 */
	public static int calculate(List<String> s) {
		Stack<String> stack = new Stack<>();
		for (String item : s) {
			if (item.matches("\\d+")) {
				stack.push(item);
			} else {
				int num1 = Integer.parseInt(stack.pop());
				int num2 = Integer.parseInt(stack.pop());
				int res = 0;
				if (item.equals("+")) {
					res = num2 + num1;
				} else if (item.equals("-")) {
					res = num2 - num1;
				} else if (item.equals("*")) {
					res = num2 * num1;
				} else if (item.equals("/")) {
					res = num2 / num1;
				} else {
					throw new RuntimeException("运算符有误");
				}
				stack.push("" + res);
			}
		}
		return Integer.parseInt(stack.pop());
	}
}

3.应用场景 一般用 stack 对表达式求值时,都会先将中缀表达式转化为逆波兰表达式

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 字符串的压缩以及解压缩

    shengjk1
  • 写给大忙人的Flink的Data Types

    二、Flink 是如何处理 Data Type 的 首先Flink会根据自身的序列化器进行序列化,如果不行,则默认回退到 Kryo 序列化器进行序列化。

    shengjk1
  • Spark Streaming 中使用 zookeeper 保存 offset 并重用 Java版

    最近中使用spark Streaming +kafka,由于涉及到金额,所以需要保证at only one, 而网上关于java版的kafka offset...

    shengjk1
  • 小瓜牛漫谈 — String

    String 类在 Java 中代表字符串。Java 程序中的所有字符串字面值(如 "abc" )都作为此类的实例实现。 1 public static voi...

    猿人谷
  • Java学习day16---人际关系

    曼路
  • 探秘Java中的String、StringBuilder以及StringBuffer

      相信String这个类是Java中使用得最频繁的类之一,并且又是各大公司面试喜欢问到的地方,今天就来和大家一起学习一下String、StringBuilde...

    Java团长
  • 你真的懂Java中的String、StringBuilder和StringBuffer吗?

    相信String这个类是Java中使用得最频繁的类之一,并且又是各大公司面试喜欢问到的地方,今天就来和大家一起学习一下String、StringBui...

    java思维导图
  • 你真的懂Java中的String、StringBuilder和StringBuffer吗?

    相信String这个类是Java中使用得最频繁的类之一,并且又是各大公司面试喜欢问到的地方,今天就来和大家一起学习一下String、StringBui...

    黄泽杰
  • httpclient爬虫爬取汉字拼音等信息

    下面是使用httpclient爬虫爬取某个网站的汉字相关信息的实践代码,中间遇到了一些字符格式的问题。之前被同事见过用html解析类来抓取页面信息,而不是像我现...

    FunTester
  • 深入理解String类

    String是java中的字符串。String类是不可变的,对String类的任何改变,都是返回一个新的String类对象。String不属于8种基本数据类型,...

    栋先生

扫码关注云+社区

领取腾讯云代金券