专栏首页编程坑太多java-逆波兰算法

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),作者:看更多☞

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 『互联网架构』软件架构-解密电商系统营销-会员模块业务(73)

    解决方案是:类似新华字典一样,redis里面针对某个活动只存储key值,内容保存在JVM cache中。因为目前都是存在JVM中,如果是分布式同步下,需要使用z...

    IT故事会
  • 『互联网架构』软件架构-Spring boot集成模板引擎swagger2实现(87)

    系统可以直接访问的路径,且路径下的所有文件均可被用户直接读取。Spring Boot默认提供静态资源目录位置需置于classpath下,目录名需符合如下规则:/...

    IT故事会
  • 世界难题-JAVA为什么要生成Class文件

    IT故事会
  • 42. Python Queue 模

    Queue对象实现一个fifo队列(其他的还有lifo、priority队列,这里不再介绍)。

    py3study
  • STL学习笔记(7)常用容器 queue

    Queue 是一种先进先出(First In First Out,FIFO)的数据结构,它有两个出口,queue 容器允许从一端新增元素,从另 一端移除元素。 ...

    轻舞飞扬SR
  • 如何自己实现一个队列

    队列是一种先进先出的数据结构,也是常见的数据结构之一。日常生活中的排队买东西就是一种典型的队列,而在购票系统也需要一个队列处理用户的购票请求,当然这里的队列就复...

    编程珠玑
  • 【转载】用队列求解迷宫最短路径及其应用(围住神经猫)

    问题 给定一个M×N的迷宫图,求一条从指定入口到出口的最短路径.假设迷宫图如图所示(M=8, N=8) ? 对于图中的每个方块,空白表示通道,阴影表示墙。所...

    李海彬
  • 【Rust日报】 2019-08-08:q 框架 - 通用队列自动机运行时实现

    这个库的作用是这个,随着数据的增多,想要从各种数据中识别出用户的关键(敏感)信息,就越来越困难,必须使用一定的工具来进行自动化处理。而这个算法就在这个过程中起作...

    MikeLoveRust
  • RabbitMQ入门-Routing直连模式

    Hello World模式,告诉我们如何一对一发送和接收消息; Work模式,告诉我们如何多管齐下高效的消费消息; Publish/Subscribe模式,告...

    JackieZheng
  • Java Getter和Setter

    Author:杭州电子科技大学 2016级管理学院 工商管理 唐涛 16011324@hdu.edu.cn

    用户3906512

扫码关注云+社区

领取腾讯云代金券