文档章节

后缀表达式转换及计算

 言不莫
发布于 2016/01/03 14:13
字数 1721
阅读 9
收藏 1
点赞 0
评论 0

1、介绍

    中缀表达式:( ( 78 - 72 ) * 4 - ( 1 + 3 ) / 2 ) * 7

      后缀表达式:78, 72, -, 4, *, 1, 3, +, 2, /, -, 7, *(前缀表达式与后缀表达式相反,这里不做介绍)

中缀表达式便于记忆,容易理解,但是计算机不容易理解,毕竟计算机全是 只认识01,不能理解复杂的逻辑,所以,将中缀表达式装换成后缀表达式,便于程序处理。

2、算法思想

2.1、中缀----后缀

 (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
 (2) 从左至右扫描中缀表达式;
 (3) 遇到操作数时,将其压入S2;
 (4) 遇到运算符时,比较其与S1栈顶运算符的优先级:
 (4-1) 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
 (4-2) 否则,若优先级比栈顶运算符的高,也将运算符压入S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);
 (4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
 (5) 遇到括号时:
 (5-1) 如果是左括号“(”,则直接压入S1;
 (5-2) 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;
 (6) 重复步骤(2)至(5),直到表达式的最右边;
 (7) 将S1中剩余的运算符依次弹出并压入S2;
 (8) 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。

2.2、后缀计算

        从左至右扫描表达式,遇到数字时,将数字压入堆栈,
 遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;
 重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。

3 Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import java.util.regex.Pattern;
/**
 * 中缀表达式得到后缀表达式
 * @author yanbu
 *
 */
public class MidToSuffix {
 
 /*将中缀表达式转换为后缀表达式: 核心思想
 与转换为前缀表达式相似,遵循以下步骤:
 (1) 初始化两个栈:运算符栈S1和储存中间结果的栈S2;
 (2) 从左至右扫描中缀表达式;
 (3) 遇到操作数时,将其压入S2;
 (4) 遇到运算符时,比较其与S1栈顶运算符的优先级:
 (4-1) 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
 (4-2) 否则,若优先级比栈顶运算符的高,也将运算符压入S1(注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况);
 (4-3) 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;
 (5) 遇到括号时:
 (5-1) 如果是左括号“(”,则直接压入S1;
 (5-2) 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;
 (6) 重复步骤(2)至(5),直到表达式的最右边;
 (7) 将S1中剩余的运算符依次弹出并压入S2;
 (8) 依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。*/
 
 /**
  * 运算符栈S1
  */
 Stack<String> s1 = new Stack<>();
 
 /**
  * 中间结果的栈S2
  */
 Stack<Object> s2 = new Stack<>();
 
 /**
  * 存储中缀表达式  格式自己定义
  * 这里每个表达式元素之间均以空格隔开
  */
 List<String> exps = new ArrayList<>();
 
 String expression;
 
 /**
  * 存储操作符优先级
  */
 Map<String, Integer> op = new HashMap<String, Integer>();
 
 public MidToSuffix(){
  op.put("+", 1);
  op.put("-", 1);
  op.put("*", 2);
  op.put("/", 2);
 }
 
 
 public void dealExps(){
  String[] exs = expression.split(" ");
  for (String exp : exs) {
   if(!exp.trim().equals("")){
    this.exps.add(exp.trim());
   }
  }
 }
 
 /**
  * 从左至右扫描中缀表达式
  */
 public void initStacl(){
  
  for (String exp : exps) {
   System.out.println("s1:" + s1 +"     " + "s2:" + s2);
   
   switch (exp) {
   case "(":  //处理括号()--参考操作(5)
    s1.push(exp);
    break;
   case ")":
    s1ToS2();
    break;
   default:
    op4(exp);
    break;
   }
  }
  
  s1ToS2(); 
  
 }
 
 /**
  * 操作(5),括号处理
  * 依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃;
  * /n同时可用于s1元素全部入栈S2
  */
 public void s1ToS2(){
  while(!s1.empty()){
   String ops = s1.pop();
   if(ops.equals("(")){
    return;
   }
   s2.push(ops);
  }
 }
 
 /**
  * 操作(4)
  * @param exp
  */
 public void op4(String exp){
  //参考操作(4)
  if(Pattern.matches("^[0-9]*$", exp)){ //遇到操作数时,将其压入S2;
   s2.push(Integer.parseInt(exp));
  }else{
   if(s1.isEmpty() || s1.peek().equals("(")){  //s1为空,操作符入栈S1
    s1.push(exp);
   }else{
    if(op.get(exp) > op.get(s1.peek())){  //比较操作符优先级,大于直接入栈  否则栈s1顶元素出栈,该操作符入栈
     s1.push(exp);
    }else{
     s2.push(s1.pop()); //栈顶元素出栈
     s1.push(exp); //操作符入栈
    }
   }
  }
 }
 
 public void setExpression(String expression){
  this.expression = expression;
 }
 
 /**
  * 获取后缀表达式
  * @param expression
  * @return
  */
 public  Stack<Object> getSuffix(String expression){
  setExpression(expression);
  dealExps();
  initStacl();
  return this.s2;
 }
 
}

 

import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
/**
 * 计算后缀表达式
 * @author yanbu
 */
public class CpuSuffix {
 
 MidToSuffix midToSuffix = new MidToSuffix();
 
 /** 核心思想
  * 从左至右扫描表达式,
  * 遇到数字时,将数字压入堆栈,
  * 遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 op 栈顶元素),并将结果入栈;
  * 重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
  * @param args
  */
 
 /**
  * 用于存放计算结果
  */
 public Stack<Object> s1 = new Stack<>();
 
 
 
 public void initSuffix(String MidExp){
  Stack<Object> stack = midToSuffix.getSuffix(MidExp);
  System.out.println("suffix:" + stack);
  Set<String> op = midToSuffix.op.keySet();
  for (Object object : stack.toArray()) {
   System.err.println(s1);
   if(op.contains(object)){
    Integer num2 = (Integer)s1.pop();
    Integer num1 = (Integer)s1.pop();
    s1.push(op(object.toString(),num1,num2));
   }else{
    s1.push(object);
   }
  }
  
  System.err.println(s1);
 }
 
 public int op(String op, int num1,int num2){
  switch (op) {
  case "+":
   return num1 + num2;
  case "-":
   return num1 - num2;
  case "*":
   return num1 * num2;
  case "/":
   return num1 / num2;
  default:
   return 0;
  }
 }
 
 public static void main(String[] args) {
  CpuSuffix cpuSuffix = new CpuSuffix();
  String exp = new Scanner(System.in).nextLine();
  cpuSuffix.initSuffix(exp);
 }
}

 

Console:

( ( 78 - 72 ) * 4 - ( 1 + 3 ) / 2 ) * 7
s1:[]     s2:[]
s1:[(]     s2:[]
s1:[(, (]     s2:[]
s1:[(, (]     s2:[78]
s1:[(, (, -]     s2:[78]
s1:[(, (, -]     s2:[78, 72]
s1:[(]     s2:[78, 72, -]
s1:[(, *]     s2:[78, 72, -]
s1:[(, *]     s2:[78, 72, -, 4]
s1:[(, -]     s2:[78, 72, -, 4, *]
s1:[(, -, (]     s2:[78, 72, -, 4, *]
s1:[(, -, (]     s2:[78, 72, -, 4, *, 1]
s1:[(, -, (, +]     s2:[78, 72, -, 4, *, 1]
s1:[(, -, (, +]     s2:[78, 72, -, 4, *, 1, 3]
s1:[(, -]     s2:[78, 72, -, 4, *, 1, 3, +]
s1:[(, -, /]     s2:[78, 72, -, 4, *, 1, 3, +]
s1:[(, -, /]     s2:[78, 72, -, 4, *, 1, 3, +, 2]
s1:[]     s2:[78, 72, -, 4, *, 1, 3, +, 2, /, -]
s1:[*]     s2:[78, 72, -, 4, *, 1, 3, +, 2, /, -]
suffix:[78, 72, -, 4, *, 1, 3, +, 2, /, -, 7, *]
[]
[78]
[78, 72]
[6]
[6, 4]
[24]
[24, 1]
[24, 1, 3]
[24, 4]
[24, 4, 2]
[24, 2]
[22]
[22, 7]
[154]

 

 

© 著作权归作者所有

共有 人打赏支持
粉丝 0
博文 2
码字总数 2424
作品 0
南京
数据结构-栈应用(中缀转后缀并计算结果)

关于中缀和后缀表达式基础概念自行百度。 对于中缀转后缀表达式并计算结果思路可归纳为以下: 1、将每个数据当做一个结构体,包含对应的类型以及数值; 2、对于给定的中缀表达式,转为结构体数...

sssssuuuuu666 ⋅ 2017/12/19 ⋅ 0

Java数据结构和算法(六)——前缀、中缀、后缀表达式

前面我们介绍了三种数据结构,第一种数组主要用作数据存储,但是后面的两种栈和队列我们说主要作为程序功能实现的辅助工具,其中在介绍栈时我们知道栈可以用来做单词逆序,匹配关键字符等等,...

architect刘源源 ⋅ 02/23 ⋅ 1

phoenixor/rpn.js

rpn.js 功能概述 数学运算表达式分3种: 1.前缀表达式(波兰式Prefix Expression):运算符在操作数之前。 2.中缀表达式(Infix Expression):一种通用的算术或逻辑公式表示方法,操作符以中...

phoenixor ⋅ 04/01 ⋅ 0

前缀、中缀、后缀表达式

前缀、中缀、后缀表达式,它们之间的区别在于运算符相对与操作数的位置不同:前缀表达式的运算符位于与其相关的操作数之前;中缀和后缀同理。对计算机来说中缀表达式是很复杂的,因此计算表达...

silenceyawen ⋅ 2016/10/16 ⋅ 0

深入理解前缀、中缀、后缀表达式

1.我们首先来看一下,什么是前缀、中缀、后缀表达式: 中缀表达式: 2 - 3 4 后缀表达式:2 3 4 - 前缀表达式:- 2 * 3 4 简单介绍下,前中后的划分依据为两个数字的操作符处于两个数字的前面...

Lucus_Guo ⋅ 2015/09/16 ⋅ 0

nyoj 267 郁闷的C小加(二)中缀表达式变后缀表达式并计算值

郁闷的C小加(二) xiewuqiang 这道题真的是……唉,一把辛酸泪,没爱了,用的队列,看的别人的代码用的队列,但是一直程序有错误,然后忽略了数组的循环直接将i加了,但是队列得出队列 #inc...

dear_jia ⋅ 05/08 ⋅ 0

后缀表达式的计算

1、栈 栈是一种只允许一端操作的线性数据结构,具有LIFO(last in first out)的特点,具有广泛的应用,如我在游戏编程模式--命令模式(2)中使用栈的结构来实验撤销、重做功能。现在打算用栈结构...

王奥宇 ⋅ 2017/12/06 ⋅ 0

《数据结构与算法》之将中缀表达式转换为后缀表达式(8)

表达式的三种形式: 中缀表达式:运算符放在两个运算对象中间,如:(2+1)3 后缀表达式:不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考...

lixiyuan ⋅ 2014/04/16 ⋅ 0

数据结构与算法 - 3.3.3.2 后缀表达式

3.3.3.2 后缀表达式 假设我们有一个便携计算器并需要计算一趟外出购物的花费。公式如下: 4.99 1.06 + 5.99 + 6.99 1.06 = ? 该例的典型计算顺序是:1. 将4.99和1.06相乘并存入A12. 然后将5...

邪恶的小Y ⋅ 2016/06/15 ⋅ 3

Java 四则运算表达式求解

最近写了一个计算器,便将其中的核心模块——表达式求值这一块稍微封装了一下,以便以后能更好的代码复用,在此我想说一下我的感悟,写程序的时候尽量将那些能单独成为模块的尽量用函数或者类...

晨曦之光 ⋅ 2012/05/23 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 22分钟前 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 46分钟前 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

实验楼—MySQL基础课程-挑战3实验报告

按照文档要求创建数据库 sudo sercice mysql startwget http://labfile.oss.aliyuncs.com/courses/9/createdb2.sqlvim /home/shiyanlou/createdb2.sql#查看下数据库代码 代码创建了grade......

zhangjin7 ⋅ 昨天 ⋅ 0

一起读书《深入浅出nodejs》-node模块机制

node 模块机制 前言 说到node,就不免得提到JavaScript。JavaScript自诞生以来,经历了工具类库、组件库、前端框架、前端应用的变迁。通过无数开发人员的努力,JavaScript不断被类聚和抽象,...

小草先森 ⋅ 昨天 ⋅ 0

Java桌球小游戏

其实算不上一个游戏,就是两张图片,不停的重画,改变ball图片的位置。一个左右直线碰撞的,一个有角度碰撞的。 左右直线碰撞 package com.bjsxt.test;import javax.swing.*;import j...

森林之下 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部