java-逆波兰算法

四则运算是栈的重要应用之一

中缀表达式转后缀表达式(逆波兰算法)过程 从左到右遍历中缀表达式 数字直接输出为后缀表达式一部分 如果是符号,则判断与栈顶元素的优先级 高于栈顶元素优先级直接入栈 低于或等于栈顶优先级栈顶元素出栈并输出为后缀表达式一部分(注意这里是递归比较栈顶元素的优先级并出栈),最后将当前元素入栈 直到遍历完中缀表达式,最终输出后缀表达式 下面是自己的实现源码

package com.yhq.demospringboot;
import org.apache.commons.lang3.StringUtils;
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
/**
 * yanghq
 * 2018/3/12
 */
public class PreToAfterUtil {
private static String leftChar = "(";
private static String rightChar = ")";
private static Map<String, Integer> operationSymbolMap = new HashMap<>();
static {
        //初始化符号和优先级
        operationSymbolMap.put(")",00); //右括号需匹配左括号,故优先级最低
        operationSymbolMap.put("+",10);
        operationSymbolMap.put("-",10);
        operationSymbolMap.put("*",20);
        operationSymbolMap.put("/",20);
        operationSymbolMap.put("(",30);
}
/**
 * 中缀表达式转化为后缀表达式
 * @param strings
 * @return
 */
public Queue parsePre(String[] strings) {
        Stack<String> preStack = new Stack<String>();
        Queue<String> queue = new LinkedBlockingQueue();
        int i = 0;
        while(i<strings.length && Objects.nonNull(strings[i])) {
                if(StringUtils.isNumeric(strings[i])) {
                        queue.add(strings[i]);
                }else if(StringUtils.isNotEmpty(strings[i])) {
                        if(preStack.isEmpty()) {
                                preStack.push(strings[i]);
                        } else {
                                String top = preStack.pop();
                                if(comparePriority(strings[i], top) < 0) {
                                        if(top.equals(leftChar)) {
                                                preStack.push(top);
                                                preStack.push(strings[i]);
                                        }else if(strings[i].equals(rightChar)) {
                                                appendTo(queue, top);
                                                preStack.pop();
                                        } else{
                                                appendTo(queue, top);
                                                popPre(preStack, strings[i], queue);
                                                preStack.push(strings[i]); //当前元素入栈
                                        }
                                } else {
                                        preStack.push(top);
                                        preStack.push(strings[i]);
                                }
                        }
                }
                i++;
        }
        while (!preStack.isEmpty()) {
                queue.add(preStack.pop());
        }
        return queue;
}
/**
 * 递归比较当前元素与栈顶元素优先级
 * @param preStatck
 * @param charTemp
 * @param queue
 */
public void popPre(Stack<String> preStatck, String charTemp, Queue queue) {
        if(!preStatck.isEmpty()) {
                String top = preStatck.pop();
                if(comparePriority(charTemp, top) <= 0) {
                        //低于栈顶元素,成为后缀表达式一部分
                        appendTo(queue, top);
                        popPre(preStatck, charTemp, queue);
                } else {
                        preStatck.push(top);
                }
        }
}
private void appendTo(Queue queue, String s) {
        if(!s.equals(leftChar) && !s.equals(rightChar)) {
                queue.add(s);
        }
}
/**
 * 比较优先级
 * @param start
 * @param to
 * @return
 */
private int comparePriority(String start, String to) {
        return operationSymbolMap.get(start).compareTo(operationSymbolMap.get(to));
}
/**
 * 计算后缀表达式结果
 * @param queue
 * @return
 */
public int computeResult(Queue<String> queue) {
        int result = 0;
        if(Objects.isNull(queue)) {
                return result;
        }
        String s = queue.poll();
        Stack<Integer> stack = new Stack();
        while(Objects.nonNull(s)) {
                if(StringUtils.isNumeric(s)) {
                        stack.push(Integer.valueOf(s));
                }else if(!StringUtils.isEmpty(s)) {
                        int first = 0;
                        int second = 0;
                        switch (s) {
                                case "+" :
                                        first = stack.pop();
                                        second = stack.pop();
                                        result = first + second;
                                        stack.push(result);
                                        break;
                                case "-" :
                                        first = stack.pop();
                                        second = stack.pop();
                                        result = second - first;
                                        stack.push(result);
                                        break;
                                case "*" :
                                        first = stack.pop();
                                        second = stack.pop();
                                        result = first * second;
                                        stack.push(result);
                                        break;
                                case "/" :
                                        first = stack.pop();
                                        second = stack.pop();
                                        result = second/first;
                                        stack.push(result);
                                        break;
                        }
                }
                s = queue.poll();
        }
        return result;
}
/**
 * 测试
 * @param args
 */
public static void main(String[] args) {
        String[] pre = new String[]{"8","+","(","6","-","1",")","*","2","+","10","/","2"};
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < pre.length; i++) {
                sb.append(pre[i]);
        }
        System.out.println("前缀表达式:" + sb.toString());
        Queue queue = new PreToAfterUtil().parsePre(pre);
        System.out.println("后缀表达式:" + queue.toString());
        System.out.println("后缀表达式计算结果:" + new PreToAfterUtil().computeResult(queue));
}
}
输出结果展示
前缀表达式:8+(6-1)*2+10/2
后缀表达式:[8, 6, 1, -, 2, *, +, 10, 2, /, +]
后缀表达式计算结果:23

原文发布于微信公众号 - 编程坑太多(idig88)

原文发表时间:2018-03-15

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏静默虚空的博客

[Java 基础]字符串

String类 实例化String对象 String 对象初始化方式有多种。 如下代码中,各种初始化方式的效果是一样的,初始化后,String 对象的内容为 "...

1905
来自专栏CDA数据分析师

一文读懂如何用 Python 实现6种排序算法

总结了一下常见集中排序的算法 ? 归并排序 归并排序也称合并排序,是分治法的典型应用。分治思想是将每个问题分解成个个小问题,将每个小问题解决,然后合并。 具体的...

22010
来自专栏互联网杂技

javascript大法好,不用记

数组的操作 ---- Array.prototype.toString ( ) 把数组转变为字符串,返回字符串,arr.toString(); ---- Arr...

3717
来自专栏浪淘沙

java初级笔记----API

一、类Object java.lang.Object 是类层次结构的根类,每个类都使用object作为超类。所有对象(包括数组)都实现这个类...

1494
来自专栏和蔼的张星的图像处理专栏

646. 第一个独特字符位置

给出一个字符串。找到字符串中第一个不重复的字符然后返回它的下标。如果不存在这样的字符,返回 -1。 样例 给出字符串 s = "lintcode",返回 0...

1022
来自专栏Petrichor的专栏

tensorflow编程: Control Flow

经验证,a1 = t 得到的是 t,a2 = tf.identity(t) 得到的不是 t ,只是 t 的副本。这样有利于用副本进行运算而不引起 原tensor...

1825
来自专栏PPV课数据科学社区

一文读懂如何用 Python 实现6种排序算法

原文链接:https://my.oschina.net/liuyuantao/blog/749329 总结了一下常见集中排序的算法 ? 归并排序 归并排序也称合...

3797
来自专栏linux驱动个人学习

动态绑定与静态绑定

为了支持c++的多态性,才用了动态绑定和静态绑定。理解他们的区别有助于更好的理解多态性,以及在编程的过程中避免犯错误。 需要理解四个名词: 1、对象的静态类型:...

3363
来自专栏小樱的经验随笔

【Java学习笔记之二十】final关键字在Java继承中的用法小结

谈到final关键字,想必很多人都不陌生,在使用匿名内部类的时候可能会经常用到final关键字。另外,Java中的String类就是一个final类,那么今天我...

2718
来自专栏吾爱乐享

java学习之string类的字符串大小写之间的转换

1303

扫码关注云+社区

领取腾讯云代金券