java数据结构与算法之中缀表达式转为后缀表达式的方法

本文实例讲述了java数据结构与算法之中缀表达式转为后缀表达式的方法。分享给大家供大家参考,具体如下:

//stack
public class StackX {
  private int top;
  private char[] stackArray;
  private int maxSize;
  //constructor
  public StackX(int maxSize){
    this.maxSize = maxSize;
    this.top = -1;
    stackArray = new char[this.maxSize];
  }
  //put item on top of stack
  public void push(char push){
    stackArray[++top] = push;
  }
  //take item from top of stack
  public char pop(){
    return stackArray[top--];
  }
  //peek the top item from stack
  public char peek(){
    return stackArray[top];
  }
  //peek the character at index n
  public char peekN(int index){
    return stackArray[index];
  }
  //true if stack is empty
  public boolean isEmpty(){
    return (top == -1);
  }
  //return stack size
  public int size(){
    return top+1;
  }
}
//InToPost
public class InToPost {
  private StackX myStack;
  private String input;
  private String outPut="";
  //constructor
  public InToPost(String input){
    this.input = input;
    myStack = new StackX(this.input.length());
  }
  //do translation to postFix
  public String doTrans(){
    for(int i=0; i<input.length(); i++){
      char ch = input.charAt(i);
      switch(ch){
      case '+':
      case '-':
        this.getOper(ch,1);
        break;
      case '*':
      case '/':
        this.getOper(ch,2);
        break;
      case '(':
        this.getOper(ch, 3);
        break;
      case ')':
        this.getOper(ch, 4);
        break;
      default:
        this.outPut = this.outPut + ch;
      }
    }
    while(!this.myStack.isEmpty()){
      this.outPut = this.outPut + this.myStack.pop();
    }
    return this.outPut;
  }
  //get operator from input
  public void getOper(char ch, int prect1){
    char temp;
    if(this.myStack.isEmpty()||prect1==3){
      this.myStack.push(ch);
    }
    else if(prect1==4){
      while(!this.myStack.isEmpty()){
        temp = this.myStack.pop();
        if(temp=='(')continue;
        this.outPut = this.outPut + temp;
      }
    }
    else if(prect1==1){
      temp = this.myStack.peek();
      if(temp=='(') this.myStack.push(ch);
      else{
        this.outPut = this.outPut + this.myStack.pop();
        this.myStack.push(ch);
      }
    }
    else{
      temp = this.myStack.peek();
      if(temp=='('||temp=='+'||temp=='-') this.myStack.push(ch);
      else{
        this.outPut = this.outPut + this.myStack.pop();
      }
    }
  }
}
//Test
public class TestInToPost {
  private static InToPost inToPost;
  private static String str;
  public static void main(String []args){
    str = "((A+B)*C)-D";
    inToPost = new InToPost(str);
    System.out.println(inToPost.doTrans());
  }
}

PS:算法实现不是很完善,有些复杂的表达式解析要出错,写出来做个纪念!

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

(0)

相关推荐

  • java实现数据结构单链表示例(java单链表)

    复制代码 代码如下: /** * 单向链表 * */public class NodeList<E> { private static class Node<E> { // 节点类  E data; // 节点上的数据  Node<E> next; // 指向下一个节点 Node(E e) {   this.data = e;   this.next = null;  } } private Node<E> head; // 链表的头节点 private N

  • Java模拟单链表和双端链表数据结构的实例讲解

    模拟单链表 线性表: 线性表(亦作顺序表)是最基本.最简单.也是最常用的一种数据结构. 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的. 线性表的逻辑结构简单,便于实现和操作. 在实际应用中,线性表都是以栈.队列.字符串等特殊线性表的形式来使用的. 线性结构的基本特征为: 1.集合中必存在唯一的一个"第一元素": 2.集合中必存在唯一的一个 "最后元素" : 3.除最后一个元素之外,均有 唯一的后继(后件):

  • Java中二叉树数据结构的实现示例

    来看一个具体的习题实践: 题目 根据二叉树前序遍历序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,构建二叉树,并且用前序.中序.后序进行遍历 代码 import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 静态内部类,定义二叉树节点 */ static class TreeNode { public Str

  • Java中使用数组实现栈数据结构实例

    栈是Java语言中最重要的数据结构之一,它的实现,至少应该包括以下几个方法: 1.pop() 出栈操作,弹出栈顶元素. 2.push(E e) 入栈操作 3.peek() 查看栈顶元素 4.isEmpty() 栈是否为空 另外,实现一个栈,还应该考虑到几个问题: 1.栈的初始大小以及栈满以后如何新增栈空间 2.对栈进行更新时需要进行同步 简单示例,使用数组实现栈,代码如下: 复制代码 代码如下: public class Stack<E> { // Java 不支持泛型数组,如需使用,请使用J

  • java数据结构之java实现栈

    复制代码 代码如下: import java.util.Arrays; /** * 栈的实现<br> * @author Skip * @version 1.0 */public class Stack<T> { private int size;    //栈中元素的个数 private Object[] arr;  //底层数组 private final int defaultLength = 200; //默认长度 /**  * 无参构造,使用默认长度初始化数组  */ p

  • java数据结构之实现双向链表的示例

    复制代码 代码如下: /** * 双向链表的实现 * @author Skip * @version 1.0 */public class DoubleNodeList<T> { //节点类 private static class Node<T>{  Node<T> perv;  //前节点  Node<T> next;  //后节点  T data;    //数据 public Node(T t){   this.data = t;  } } priv

  • java数据结构实现顺序表示例

    复制代码 代码如下: import java.util.Arrays;/** * 顺序线性表的实现 */public class LineList<E>{ private int size;   //长度 private Object[] array;  //底层数组 private final int default_length=16; //默认长度 /**  * 无参构造方法  */ public LineList(){  size = 0;  //使用默认长度构造数组  array =

  • 剖析Java中HashMap数据结构的源码及其性能优化

    存储结构 首先,HashMap是基于哈希表存储的.它内部有一个数组,当元素要存储的时候,先计算其key的哈希值,根据哈希值找到元素在数组中对应的下标.如果这个位置没有元素,就直接把当前元素放进去,如果有元素了(这里记为A),就把当前元素链接到元素A的前面,然后把当前元素放入数组中.所以在Hashmap中,数组其实保存的是链表的首节点.下面是百度百科的一张图: 如上图,每个元素是一个Entry对象,在其中保存了元素的key和value,还有一个指针可用于指向下一个对象.所有哈希值相同的key(也就

  • Java模拟栈和队列数据结构的基本示例讲解

    栈和队列: 一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建: 访问受限,在特定时刻,只有一个数据可被读取或删除: 是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组.链表来实现栈. 模拟栈结构 同时,只允许一个数据被访问,后进先出 对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数,操作比较快 例,使用数组作为栈的存储结构 public class StackS<T> { private int max; private T[] ary; priv

  • Java数据结构(线性表)详解

    线性表的链式存储与实现 实现线性表的另一种方法是链式存储,即用指针将存储线性表中数据元素的那些单元依次串联在一起.这种方法避免了在数组中用连续的单元存储元素的缺点,因而在执行插入或 删除运算时,不再需要移动元素来腾出空间或填补空缺.然而我们为此付出的代价是,需要在每个单元中设置指针来表示表中元素之间的逻辑关系,因而增加了额外的存储空间的开销. 单链表 链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个域是指向其他单元的指针.这里具有

  • Java模拟有序链表数据结构的示例

    有序链表: 按关键值排序.删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置. 插入时需要比较O(N),平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1), 如果一个应用需要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择 优先级队列 可以使用有序链表来实现 有序链表的插入排序: 对一个无序数组,用有序链表来排序,比较的时间级还是O(N^2) 复制时间级为O(2*N),因为复制的次数较少,第一次放进链表数据移动N次,再从链表复制到数组,

随机推荐