图片 14

栈和队列,利用栈深入分析算术表明式

By admin in 编程 on 2019年5月21日

Q: 栈、队列与数组的分裂?

A: 本篇主要涉及二种多少存款和储蓄类型:栈、队列和先行级队列,它与数组首要有如下两个组别:

A: (1)程序猿工具 
数组和别的的组织(栈、队列、链表、树等等)都适用于数据库应用中作为数据记录。它们常用于记录那三个对应于实际世界的对象和移动的数目,如职员档案等,那个构造有利于数据的拜访:它们易于实行插队、删除和查找特定数据项的操作。 
但是,本篇要上课的数据结谈判算法更加多的是作为技师的工具来使用。它们首要作为观念算法的帮助工具,而不是全然的数据存款和储蓄工具。这么些数据结构的生命周期比那二个数据库类型的布局要短得多。在先后操作施行时期它们才被创立,常常用它们去推行某项特殊的天职;当成功职责之后,它们则被灭绝。

A: (2)受限访问 
在数组中,若知道数码项的下标,便得以及时访问该多少项;而在本篇的数据结构中,访问是受限制的,即在特定时刻唯有贰个数量项能够被读取可能去除。 
这么些构造接口的宏图加强了这种受限访问,访问别的数据项反驳上是不允许的。

A: (三)尤其空虚 
栈、队列和优先队列是比数组和任何数据存款和储蓄结构更为抽象的组织。主借使由此接口对栈、队列和前期队列实行定义,接口表明了它们能够完成的操作,而重大完毕机制对用户来讲是不可知的。 
比如说:栈的落实机制得以用数组达成,本篇的演示正是那样管理的,但它也能够用链表来兑现。优先级队列的中间贯彻可以用数组或壹种极度的树-堆来落到实处。

在编写制定编写翻译器时平时索要贯彻对算术表明式的深入分析,然则对于Computer的算法来讲假设直接求解算术表达式的值,依然相当困难的。由此分析算术表明式平时分步落到实处:

ArrayList和LinkedList的兑现方式

ArrayList的尾巴部分实现是足以进步的数组,LinkedList的底层是使用了双链表。从尾巴部分实现来看,我们得以了解,ArrayList
获取要素的日子复杂度仅为常数,而 插入
删除的年华复杂度都为线性时间复杂度O(n)。而LinkedList则刚刚相反,因为尾巴部分是链表,所以
插入删除的小时复杂度为常数,而
获取要素的时刻复杂度却是线性时间复杂度。

其它,ArrayList和LinkedList的contains和remove方法的年月复杂度都为线性时间复杂度O(n),对于contains方法来讲,ArrayList和linkedList都亟待遍历操作来实现contains方法,所以时间复杂度都以线性的;对于remove操作,ArrayList删除后要求活动成分,所以时间复杂度是线性的,而LinkedList的remove操作纵然是常数时间的,但是查找到成分的日子复杂度是线性的,所以,对已LinkedList的remove操作来讲也是线性时间复杂的。

Q: 什么是栈?

A: 栈只允许访问三个多少项:即最终插入的数据项。移除这几个数目项技能访问倒数第3个插入的数目项,由此及彼。

一.将中缀的算术表明式转变为后缀表达式
二.测算后缀表明式的值

栈的运用–总结表明式的值

本章用Java来是落到实处多少个乘除包括+,-,*,\和括号的表达式的值,包蕴的知识点有:

  • Java语言中栈Stack和Queue的运用
  • 中缀表明式转后缀表明式的技巧
  • 计量后缀表达式的值

Java提供了栈的兑现Stack对象,它三番五次了Vector类,底层完毕是数组。Queue是贰个Java队列接口,个中提供了队列必要的法门,而LinkedList实现了Queue接口,能够使用LinkedList来达成队列操作。举例:入队操作为addinsert情势,出队操作为
poll办法,获取队头的成分为peek方法。

中缀表达式是大家常用的算术表示方法,其标识是操作符处于操作数之间。而后缀表达式是操作符处于操作数之后,并且包含的运算顺序,易于Computer进行估测计算。形象点的事例,举个例子一+二*三+(一+2)是中缀表明式,将其转换到后缀表达式为一,
二, 三, * , +, 一, 贰, +, +。其转移进度如下:

输入:1

操作:将数字一向出席到结果队列

postfix(结果队列, 从队头到队尾):1

opStack(操作符队列,从栈底到栈顶,):空

输入:+

操作:因为opStack栈为空,所以将+号如操作符栈

postfix: 1

opStack: +

输入:2

操作:将数字平素进入结果队列

postfix: 1, 2

opStack: +

输入*

操作:因为*的企图优先级大于站定+号的优先级,所以入栈

postfix: 1,2

opStack: +,*

输入3

操作:数字从来入结果 队列

postfix: 1,2,3

opStack: +,*

输入+

操作:因为+号的先行级不超过栈顶的*,所以*弹栈并且放置结果队列中;此时栈顶的仍为+号,可是输入的+号的先行级不高于栈顶的+号,所以,栈顶的+号出栈;此时栈为空,所以当前的+号入栈

postfix: 1,2,3,*,+

opStack: +

输入(

操作:对于( 的输入来讲,直接操作栈就可以,约等于说(
在入栈前比别的操作符的预先级都大;而另一中非凡景况是借使栈顶成分是(,
那么唯有)的输入才足以使其出栈,也即是或对于其它操作符来讲,它们的优先级又比已经入栈的(
的预先级大。

postfix: 1,2,3,*,+

opStack: +,(

输入1

操作:间接投入结果队列

postfix: 1,2,3,*,+,1

opStack: +,(

输入+

操作:碰着栈顶为(, 所以直接+号入操作符栈

postfix: 1,2,3,*,+

opStack: +,(,+

输入2

操作:直接参与结果队列

postfix: 1,2,3,*,+,1,2

opStack: +,(,+

输入)

操作:对于)的输入,应该对操作符栈进行弹栈,直至遭遇(,
弹栈才甘休,那也实属,)的在入栈前的预先级比其余操作的开始时期级都低。在要是表明式合法的前提下,不设有)处在栈顶的图景,)会和(一同出栈,但不会放入结果队列中。那叁次,+号和(出栈,+号进入结果队列。

postfix:1,2,3,*,+,1,2,+

opStack:+

假若操作符栈不为空,全体弹出出席结果队列

postfix: 1,2,3,*,+,1,2,+,+

opStack: 空

Q: 栈有如何实际情形?

A: 大部计算机械运输用基于栈的系统布局,当调用1个主意时,把它的重回值和参数压入栈,当方法结束重临时,哪些数据出栈。栈操作就停放在Computer中。

在规范介绍算法的达成在此以前,先介绍一些有关表明式的基础知识

算算表达式的值–Java版完成

接下去,小编将要介绍一下本人的小型计算器的落到实处,表达式的风味是富含+,-,*,/和(),并且数字是整数,能够是多位的。整个实现分为三多数:

  1. 读取优先级列表
  2. 中缀表明式转变来后缀表明式
  3. 计量后缀表明式的值

当然了,最难的片段是第二步,下边1一介绍。

  • 优先级列表

自家是用三个文书来囤积操作符和相应的优先级,每行存款和储蓄三个,选拔操作符-空格-优先级的艺术,如下:+

完全的早期级列表如下

+ 1
- 1
* 2
/ 2

应用HashMap保存优先级列表,这里涉及了什么将贰个char转化成多少个int值的进度,大家应用了先将char转化成String,然后将String转化成Integer的章程

        //读入优先级文件
        Map<Character,Integer> priority=new HashMap<Character,Integer>();
        BufferedReader breader=new BufferedReader(new FileReader("priority.txt"));
        String pline=breader.readLine();
        while(pline!=null) {
            char[] plineChar=pline.toCharArray();
            priority.put(plineChar[0], Integer.parseInt(String.valueOf(plineChar[2])));
            pline=breader.readLine();
        }
        System.out.println("优先级:"+priority);
        breader.close();
  • 中缀表达式转后缀表明式

因为数字是多位的,所以用了3个栈来numStack来记录数,并且选取八个静态方法拼接成一个整数。opStack<
Character>是用来存款和储蓄操作符的,postfix是用来存款和储蓄调换好的后缀表明式的。整个进程如下:

        //numStack用于存储存储操作数
        Stack<Integer>numStack=new Stack<>();
        //opStack用于存储操作符
        Stack<Character>opStack=new Stack<>();
        //postfix存储后缀表达式的,
        //其中有Integer和Character类型,所以用Object作为泛型参数
        Queue<Object>postfix=new LinkedList<>();
        Scanner scanner=new Scanner(System.in);
        String myExp=scanner.nextLine();
        while(myExp!=null && !"end".equalsIgnoreCase(myExp)) {
            char[] charExp=myExp.toCharArray();
            //System.out.println(charExp);
            for(char charitem:charExp) {
                switch (charitem) {
                    case '1': case '2': case '3': case '4': case '5':
                    case '6': case '7': case '8': case '9': case '0':
                        numStack.push(Integer.parseInt(String.valueOf(charitem)));
                        break;
                    case '+': case '-': case '*':
                    case '/': case '(':case ')':
                        //在遇到操作符号之前弹出数字拼接
                        pushNumber2Result(numStack, postfix);
                        if(opStack.isEmpty()) {
                            opStack.push(charitem);
                        }else {
                            //对右括号特殊处理
                            if(charitem==')'&&!opStack.isEmpty()) {
                                while(opStack.peek()!='(') {
                                    postfix.add(opStack.pop());
                                }
                                //弹出左括号
                                opStack.pop();
                            }else if(charitem=='(') {
                                opStack.push(charitem);
                            }else {
                                //对非括号的符号输入
                                //如果碰到左括号操作符号入栈
                                if(opStack.peek()=='(') {
                                    opStack.push(charitem);
                                }else if(priority.get(charitem)>priority.get(opStack.peek())) {
                                    //如果下一个操作符的优先级大于栈顶的优先级,
                                    //压栈,此时栈顶一定有操作符
                                    opStack.push(charitem);
                                }else {
                                    //否则,出栈直至当前操作符入栈
                                    //注意当栈不空的情况下比较
                                    while(!opStack.isEmpty() && priority.get(charitem)                                          <=priority.get(opStack.peek())) {
                                        postfix.add(opStack.pop());
                                    }
                                    opStack.push(charitem);
                                }
                            }
                        }

                }
            }
            pushNumber2Result(numStack, postfix);
            //注意剩余的操作符可能有多个
            while(!opStack.isEmpty()) {
                postfix.add(opStack.pop());
            }
            System.out.println(postfix);

里面,pushNumber二Result函数的概念如下:

public static void pushNumber2Result(Stack<Integer>numStack, Queue<Object>result) {
        int num=0;
        int base=1;
        while(!numStack.isEmpty()) {
            num=num+numStack.pop()*base;
            base=base*10;
        }
        //注意如果num!=0才添加进去
        if(num!=0)
            result.add(num);
    }

多少个值得注意的地方:

  1. 栈的轮回操作注意判空
  2. 操作数的丰盛如如若0的话不应该加上
  • 应用后缀表明式 总括表明式的值

            numStack.clear();
            while(!postfix.isEmpty()) {
                Object head=postfix.poll();
                if(head instanceof Integer) {
                    numStack.push((Integer)head);
                }else if(head instanceof Character){
                    Character op=(Character) head;
                    int num2=numStack.pop();
                    int num1=numStack.pop();
                    switch(op) {
                    case '+':
                        numStack.push(num1+num2);
                        break;
                    case '-':
                        numStack.push(num1-num2);
                        break;
                    case '*':
                        numStack.push(num1*num2);
                        break;
                    case '/':
                        numStack.push(num1/num2);
                        break;
                    }
                }
            }
            if(numStack.size()==1) {
                System.out.println("result:"+numStack.pop());
            }else {
                System.out.println("计算出错!");
            }
  • 测试结果

优先级:{*=2, +=1, -=1, /=2}
1+2*3+(1*2)
[1, 2, 3, *, +, 1, 2, *, +]
result:9
1+2*4-5/(1+1)
[1, 2, 4, *, +, 5, 1, 1, +, /, -]
result:7

功勋卓著告成!

Q: 栈的Java代码?

A: 在本例中,StackX类里面数据项的品种为long型,是用数组来兑现,top变量存储栈顶成分的下标。

示例: StackX.java,
StackXTest.java

基础知识

Q: 栈示例1:单词逆序?

A: 栈的第一个例子是做1件极度轻便的专门的职业:单词逆序。因为栈的后进先出(LIFO)的特点,所以字母的顺序就颠倒了。

示例:Reverser.java

1. 后缀表明式

普通算术表明式是将操作符(operator)(+,-,*,/)放在七个操作数(operands)(数字,大概表示数字的字母)中间的,由于操作符写在操作数中间,所以把这种写法称为中缀表达式.对人类来说,中缀表明式便于精通和阅读.

后缀表明式,又称作波兰(Poland)逆序表明式(Reverse Polish
Notation),它是将操作符放在操作数前边的壹种表达式的记录格局,举例A+B变成AB+,那是一种便利计算机总计的宣布式.

中缀表达式 后缀表达式
A+B-C AB+C-
A*B/C AB*C/
A+B*C ABC*+
A+B*(C-D/(E+F)) ABCDEF+/-*+

Q: 栈示例贰:分隔符相称?

A: 栈平时用于相配左分隔符和右分隔符,因为最终出现的左侧分隔符须求首先相配,那几个原理符合栈的LIFO的性子。 
下边是部分事例:

c[d]        // correct
a{b[c]d}e   // correct
a{b(c]d}e   // not correct; ] doesn’t match (
a[b{c}d]e}  // not correct; nothing matches final }
a{b(c)      // not correct; nothing matches opening {

相隔符相称程序从字符串中不停地读取字符,每回读取三个字符。若开掘它是左分隔符,将它压入栈中。当读到贰个右分隔符时,弹出栈顶的左分隔符,并且查看它是或不是和右分隔符向相称。(注:非分隔符的字符不插入栈中,只需忽略它们。)

示例:BracketChecker.java

2. 栈

栈(Stack)是Computer中采纳的可怜多的壹种数据结构,其根据先进后出的规律,能够用数组也许链表来贯彻栈,本文中正是使用数组实现八个简练的栈.


Q: 栈的成效?

A: StackX类中落到实处的栈,入栈和出栈的时间复杂度为常数O(1),
栈操作所成本的时刻不借助于于栈中多少项的个数,因而操作时间异常的短。栈无需相比和移动操作。

中缀表明式转换为后缀表明式

将中缀表明式转变为后缀表达式是分析算术表达式中最重大的一步,本文中通过观望几个示范然后计算出调换规律.

Q: 什么是队列?

A: 队列(Queue)在词典里是“排队”(waiting
line)的情致。Computer科学中,队列是1种数据结构,有一点点类似栈,只是队列中的第三个插入的数量项发轫被移除(先进先出,FIFO),而在栈中,最后插入的数码项伊始移除(LIFO)。

1. 分析

将中缀表达式调换为后缀表达式的规则和总括中缀表明式值的规则相似,无需做总结,只是把操作数和操作符重新排列为另一种方式:后缀表示法.

从左到右的扫视中缀表达式,遭遇操作数间接出口,遭受操作符则依照调换规则入栈也许输出.以将A*(B+C)的转变为例:

读取的字符 分解中缀表达式 求后缀表达式 栈中内容
A A A
+ A+ B +
B A+B AB +
* A+B* AB +*
( A+B*( AB +*(
C A+B*(C ABC +*(
A+B*(C- ABC +*(-
D A+B*(C-D ABCD +*(-
) A+B*(C-D) ABCD- +*(
A+B*(C-D) ABCD- +*(
A+B*(C-D) ABCD- +*
A+B*(C-D ABCD-* +
A+B*(C-D) ABCD-*+

从中能够看看,操作符的开头顺序在中缀表明式中是+*-,然而在后缀表明式中成为了-*+,那是因为*+的开始时期品级高,而-在括号中因故优先级比*高.

Q: 什么是循环队列?

A: 为了幸免队列不满却无法插入新数据项的难题,可以让队头队尾指针绕过到数组起先的职位,那正是循环队列。

二. 规律总括

通过阅览上边的调换例子,能够一般地计算出中缀表明式转变为后缀表明式的转移规则.

从输入中读取的字符 动作
操作数 写至输出(postfix)
左括号 ( 入栈
右括号 )

栈非空时,重复以下步骤:弹出一项,若项不为(,则写至输出,项为(,则脱离循环|
|Operator(opThis)| 若栈空,
推opThis;不然,栈非空时,重复:弹出一项,若项为(,推其入栈;或项为operator(opTop),且,若opTop<opThis,推入opTop,或opTop>=opThis,输出opTop,若opTop<opThis,则脱离循环,或项为(,推入opThis|
|未有越来越多项 |当栈非空时,弹出项目,将其出口|

Q: 队列有怎么着实际的境况?

A: 利用文字处理器,敲击二个键,而计算机又一时半刻要做任何的政工。敲击的内容不会被遗失,它会在队列中等候,知道文字管理程序一时光来读取它。利用队列有限支撑了键入内容在拍卖时其顺序不会改造。

三. 代码实现

采纳java达成上述调换进程,关键如下:

/**
 * 中缀表达式转换为后缀表达式
 *
 * @return 转换结果
 */
public String doTrans() {
    for (int j = 0; j < input.length(); j++) {
        char ch = input.charAt(j);
        theStack.displayStack("For " + ch + " ");
        switch (ch) {
            case '+':
            case '-':
                gotOper(ch, 1);
                break;
            case '*':
            case '/':
                gotOper(ch, 2);
                break;
            case '(':
                theStack.push(ch);
                break;
            case ')':
                gotParen(ch);
                break;
            default:
                output += ch;
                break;
        }
    }
    while (!theStack.isEmpty()) {
        theStack.displayStack("While ");
        output += theStack.pop();
    }
    theStack.displayStack("End ");
    return output;
}

public void gotOper(char onThis, int prec1) {
    while (!theStack.isEmpty()) {
        char onTop = theStack.pop();
        if (onTop == '(') {
            theStack.push(onTop);
            break;
        } else {
            int prec2;
            if (onTop == '+' || onTop == '-') {
                prec2 = 1;
            } else {
                prec2 = 2;
            }

            if (prec2 < prec1) {
                theStack.push(onTop);
                break;
            } else {
                output += onTop;
            }
        }
    }
    theStack.push(onThis);
}

public void gotParen(char ch) {
    while (!theStack.isEmpty()) {
        char chx = theStack.pop();
        if (chx == '(') {
            break;
        } else {
            output += chx;
        }
    }
}

Q: 队列的Java代码?

A: Queue类不但有mFront(队头)和mRear(队尾),还有队列在那之中当前数量项的个数mSize。

A: add/offer()方法 
将钦赐的因素插入此行列。不一样在于add(e)会抛出极其,offer(e)回来特殊值。

测算后缀表明式

绝对于转变来说,总括后缀表明式是相比便于的.从左到右扫描输入(后缀表明式),蒙受操作数将之入栈,每遇到3个操作符,从栈中建议八个操作数,用操作符将其实行运算,将计算结果入栈.

里头调用insert()方法,一般处境,插入操作mRear(队尾指针)加1后,在队尾指针所指的地方处插入新的多寡项。可是,当mRear指向数组的终极一个要素,即mItems.length

一职责的时候,在插入数据项在此以前,它必须再次来到数组的率先个要素前边,即mRear设置为-1,因而当mRear加一后,它等于0,是数组第多少个因素的下标值。最终,mSize加1。

A: remove()/poll()方法 
赢得并移除此行列的头。差异在于remove(e)会抛出特别,poll(e)重返特殊值。

其间调用extract()方法,该方法总是由mFront指针获得队头数据项的值,然后将mFront加一。然则,要是如此做mFront会超过数组的深浅,mFront必须绕回到数组下标为0的岗位上。注意先将重临值临时存款和储蓄起来。最终mSize减1。

A: peek()方法 
收获但不移除此队列的头;若是此队列为空,则赶回NULL_ELEMENT。

A: 示例:Queue.java

一. 代码实现

/**
 * 对后缀表达式求值
 *
 * @return 求值结果
 */
public int doParse() {
    int num1, num2, interAns = 0;
    char ch;
    theStack = new StackY(20);
    for (int j = 0; j < input.length(); j++) {
        ch = input.charAt(j);
        theStack.displayStack("" + ch + " ");
        if (ch >= '0' && ch <= '9') {
            theStack.push((ch - '0'));
        } else {
            num2 = theStack.pop();
            num1 = theStack.pop();
            switch (ch) {
                case '+':
                    interAns = num1 + num2;
                    break;
                case '-':
                    interAns = num1 - num2;
                    break;
                case '*':
                    interAns = num1 * num2;
                    break;
                case '/':
                    interAns = num1 / num2;
                    break;
                default:
                    interAns = 0;
            }
            theStack.push(interAns);
        }

    }
    interAns = theStack.pop();
    return interAns;
}

Q: 未有多少项计数字段的队列Java代码?

A: 在Queue类中含有数据项计数字段mSize会使insert()和extract()方法扩张一点额外的操作,因为拍卖insert()和remove()方法必须分别递增和递减那一个变量值。这或者算不上额外的付出,然则如若拍卖大批量的插入和移除操作,这就可能会潜移默化属性。由此,一些队列的实现不行使数据项计数的字段,而是经过mFront和mRear来测算出行列是不是为空大概满以及数额项的个数。

示例:Queue.java

括号相配

在用户输入表达式的经过中,有时会冒出左右括号不协作的情事,对于这种状态,一个神奇的算术解析器应该能够分辨出来并报错.那些实在正是括号相配的难点,也是行使栈来化解的,完毕思路如下.

算法从左到右不断扫描输入的字符串,假使为左分隔符((、[、{),间接入栈;若是为右分隔符,弹出栈顶的左分隔符,并且查看它是还是不是和右分隔符相配。如若它们不匹配则报错.若是栈中并未有左分隔符和右分隔符相称,也许直接存在着未有被相称的分隔符(栈非空),程序也报错.

Q: 队列的频率?

A: 和栈一样,队列中插入数据项和移除数据项的时日复杂度均为O(一)

壹. 代码完结

public boolean check() {
    int size = input.length();
    StackY<Character> theStack = new StackY<>(size);
    char ch, chx;
    for (int j = 0; j < size; j++) {
        ch = input.charAt(j);
        switch (ch) {
            case '(':
                theStack.push(ch);
                break;
            case ')':
                if (!theStack.isEmpty()) {
                    chx = theStack.pop();
                    if (chx != '(') return false;
                } else
                    return false;
            default:
                break;
        }
    }
    if (!theStack.isEmpty())
        return false;
    return true;
}

Q: 双端队列?

A: 

附录

Q: 优先级队列?

A: 优先级队列是不相同于先进先出队列的另①种队列。每一回从队列中抽出的是享有最高优先权的因素。

1. 说明

  • 为了落到实处方便人民群众,本算法只针对1人数的乘除有效,即12*2不能够深入分析,3*9可以剖判
  • 参照他事他说加以调查资料:Java数据结构和算法(第二版)

Q: 优先级队列有哪些实际处境?

A: 诸如,在抢先式多职务操作系统中,程序排列在初期级队列中,那样优先级最高的先后会赢得时间片并得以运转。

2. 完好无损代码

package com.lxl.stack;

import jdk.internal.org.objectweb.asm.signature.SignatureWriter;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 利用栈解析算术表达式
 *
 * @author lixiaolin
 * @createDate 2016-05-31 16:59
 */
public class InfixApp {
    public static String getString() throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        return br.readLine();
    }

    public static void main(String[] args) throws IOException {
        String input, output;
        int result;
        while (true) {
            System.out.println("Enter infix: ");
            System.out.flush();
            input = getString();
            if (input == "") {
                break;
            }
            Bracket bracket =new Bracket(input);
            if (!bracket.check()){
                System.out.println("The input is invalid...");
                break;
            }
            InToPost theTrans = new InToPost(input);
            output = theTrans.doTrans();
            System.out.println("Postfix is " + output);
            ParsePost parsePost = new ParsePost(output);
            result = parsePost.doParse();
            System.out.println("Final result is : " + result);
        }
    }
}

/**
 * 辅助栈
 *
 * @param <T>
 */
class StackY<T> {
    private int maxSize;
    private int top;
    private Object[] stackArray;

    public StackY(int maxSize) {
        this.maxSize = maxSize;
        this.top = -1;
        stackArray = new Object[maxSize];
    }

    public void push(T value) {
        stackArray[++top] = value;
    }

    public T peek() {
        return (T) stackArray[top];
    }

    public T pop() {
        return (T) stackArray[top--];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int size() {
        return top + 1;
    }

    public T peekN(int n) {
        return (T) stackArray[n];
    }

    public void displayStack(String s) {
        System.out.print(s);
        System.out.print("Stack (botton->top): ");
        for (int i = 0; i < size(); i++) {
            System.out.print(peekN(i));
            System.out.print(" ");
        }
        System.out.println("");
    }
}

class InToPost {
    private String input;
    private StackY<Character> theStack;
    private String output = "";

    public InToPost(String input) {
        this.input = input;
        theStack = new StackY(input.length());
    }

    /**
     * 中缀表达式转换为后缀表达式
     *
     * @return 转换结果
     */
    public String doTrans() {
        for (int j = 0; j < input.length(); j++) {
            char ch = input.charAt(j);
            theStack.displayStack("For " + ch + " ");
            switch (ch) {
                case '+':
                case '-':
                    gotOper(ch, 1);
                    break;
                case '*':
                case '/':
                    gotOper(ch, 2);
                    break;
                case '(':
                    theStack.push(ch);
                    break;
                case ')':
                    gotParen(ch);
                    break;
                default:
                    output += ch;
                    break;
            }
        }
        while (!theStack.isEmpty()) {
            theStack.displayStack("While ");
            output += theStack.pop();
        }
        theStack.displayStack("End ");
        return output;
    }

    public void gotOper(char onThis, int prec1) {
        while (!theStack.isEmpty()) {
            char onTop = theStack.pop();
            if (onTop == '(') {
                theStack.push(onTop);
                break;
            } else {
                int prec2;
                if (onTop == '+' || onTop == '-') {
                    prec2 = 1;
                } else {
                    prec2 = 2;
                }

                if (prec2 < prec1) {
                    theStack.push(onTop);
                    break;
                } else {
                    output += onTop;
                }
            }
        }
        theStack.push(onThis);
    }

    public void gotParen(char ch) {
        while (!theStack.isEmpty()) {
            char chx = theStack.pop();
            if (chx == '(') {
                break;
            } else {
                output += chx;
            }
        }
    }
}

class ParsePost {
    private String input;
    private StackY<Integer> theStack;

    public ParsePost(String input) {
        this.input = input;
    }

    /**
     * 对后缀表达式求值
     *
     * @return 求值结果
     */
    public int doParse() {
        int num1, num2, interAns = 0;
        char ch;
        theStack = new StackY(20);
        for (int j = 0; j < input.length(); j++) {
            ch = input.charAt(j);
            theStack.displayStack("" + ch + " ");
            if (ch >= '0' && ch <= '9') {
                theStack.push((ch - '0'));
            } else {
                num2 = theStack.pop();
                num1 = theStack.pop();
                switch (ch) {
                    case '+':
                        interAns = num1 + num2;
                        break;
                    case '-':
                        interAns = num1 - num2;
                        break;
                    case '*':
                        interAns = num1 * num2;
                        break;
                    case '/':
                        interAns = num1 / num2;
                        break;
                    default:
                        interAns = 0;
                }
                theStack.push(interAns);
            }

        }
        interAns = theStack.pop();
        return interAns;
    }
}

class Bracket {
    private String input;

    public Bracket(String input) {
        this.input = input;
    }

    public boolean check() {
        int size = input.length();
        StackY<Character> theStack = new StackY<>(size);
        char ch, chx;
        for (int j = 0; j < size; j++) {
            ch = input.charAt(j);
            switch (ch) {
                case '(':
                    theStack.push(ch);
                    break;
                case ')':
                    if (!theStack.isEmpty()) {
                        chx = theStack.pop();
                        if (chx != '(') return false;
                    } else
                        return false;
                default:
                    break;
            }
        }
        if (!theStack.isEmpty())
            return false;
        return true;
    }
}

Q: 优先级队列的Java代码?

A: 本示例使用有序数组完成优先级队列,这种办法插入极快,不过它相比较简单,适用于数据量十分的小而且不是极度重视插入速度的情状。

示例:PriorityQueue.java

A: 小小的关键字值得数据项总是数组的高等(最高下标值处),而最大的多寡项在低档(下标值为0的地方)。 
图片 1

A: 待出队的数额项总是在数组的高级,所以删除操作又快又便于。删除数据项后,队头指针下移指向队列新的高等,无需活动和比较。

A: 专注未有指针回绕,队尾指针从不移动,它连接指着数组低档的成分。

A: Font和Rear指针是为了和日常队列做相比较,实际上并没有须求它们。

A: 在数额项个数相比少,或不太关心速度的事态下,用数组完结优先级队列还足以满足必要。假若数量项大多,或速度很主要时,采取堆是更加好的选拔。

Q: 优先级队列的频率?

A: 本示例的先行级队列插入操作须要O(N)时光,而删除操作则需求O(壹)的岁月。前边将介绍怎么着通过堆来改进插入操作的时间。

Q: 怎样剖析算术表明式?

A: 对于诸如 2*(3+4) 或者 ((2+4)*7)+3*(9-5)的算术表明式,前边我们早就演示了怎么使用栈来检查分隔符是或不是相配正确,不过接下去我们将学习怎么深入分析这个算术表明式。

实则,对计算机算法来讲假设要直接求算术表明式的值照旧一定费劲,由此对此算法来说分那两步达成更易于: 

  1. 将算术表明式调换成另1种方式:后缀表明式 
  2. 计量后缀表明式的值

Q: 中缀/后缀表明式?

A: 中缀表明式:操作符放在三个操作数之间。比如A+B或A/B等。 
A: 后缀表达式:也称作逆波兰(Poland)表达式(Reverse Polish
Notation或许RPN),它是由一人波兰共和国(The Republic of Poland)的科学家发明的。操作符跟在五个操作数的末端,而且不带有括号。那样A+B
就改成AB+,A/B形成AB/。

A: 上面是中缀表达式转化为后缀表明式的事例: 
图片 2

Q: 人类是什么样计算中缀表明式?

A: 是因为Mr.
Klemmer的漫漫的教学教育,对于三+肆+伍也许三*(4+5)表明式,大家人类做起这一个题目却极其轻易。通过剖析人类怎么着总括那么些表明式的值,能够得出转化为后缀表明式的开导: 
粗略地说,分析算术表明式时,应该根据下列几条规则: 

  1. 从左到右读取算式 
    贰.
    早已读到了足以测算值得八个操作数和三个操作符时,就可以总括,并用计量结果替代那七个操作数和哪些操作符 
    三.连任那个历程–从左到右,能算即使–直到表明式的最后。

A: 示例:3 + 4 – 5

图片 3 
图片 4

A: 示例: 3 + 4 * 5 
图片 5 
图片 6

A: 示例: 3 * (4 + 5) 
图片 7 
图片 8

Q: 怎样把中缀表明式转变到后缀表明式?

A: 正如前方看到的那样,计算中缀表明式,既要向前,也要向后读表明式。将中缀表明式转变来后缀表达式的规则和总结中缀表达式的规则类似。不过依然有一点变化。

A: 将中缀表明式转换到后缀表明式不用做算术运算,它不求中缀表明式的值,只是把操作数和操作符重新排列成另一种格局。

A: 调换规则: 
图片 9

A: 示例:A+B-C 
图片 10

A: 示例:A+B*C 
图片 11

A: 示例:A*(B+C) 
图片 12

Q: 中缀表明式调换到后缀表明式的Java代码 ?

A: 示例: In2PostTransform.java

Q: 人类怎么样用后缀表明式求值?

A: 下图体现了人类是什么通过观看和铅笔在纸上总计后缀表达式的。 
示例:345+*612+/– 
图片 13

从左侧首个操作符早先,把它和它左侧相邻的多个操作数画在三个圆形里,然后使用操作符运算两个操作数并把结果写在圆形里。最大的圈子里算出来的值正是以此表明式最终的结果。

Q: 后缀说明式求值的规则?

A: 怎么技巧写三个程序来再一次刚才的求值进程吧?正如下边所描述,每蒙受3个操作符,就用它来运算在那前面最终看看的三个操作数,那就标明能够运用栈来存款和储蓄操作数。它的条条框框如下: 
图片 14

算术操作的结果被压入到栈中,在最终3个字符(一定是操作符)被读取并实行计算未来,栈里只剩贰个数额项,它正是百分百表明式的运算结果。

Q: 后缀表明式求值的Java代码?

A: 为了简化代码,这里限制只能输入1个人数的数字。 
示例:PostfixParser.java

Q: 本篇小结?

  • 栈、队列和预先级队列是有的时候用来简化有个别程序操作的数据结构。
  • 在那么些数据结构中,唯有三个数量项能够被访问。
  • 栈只允许访问最终二个布署的数据项。
  • 队列只允许访问第二个插入的数码项。
  • 队列能够兑现为循环队列,它依据数组,数组下标能够从数组末端回绕到数组的开始地点。
  • 先行级队列的重大操作是不改变地插入新数据项和移除关键字非常小(临时是最大)的多寡项。
  • 那些数据结构能够用数组实现,也得以用此外编制(举个例子链表)来促成。

Q: 参考

  1. 《Java数据结商谈算法》罗Bert Lafore 著,第5章 – 栈和队列

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 澳门新葡亰官网app 版权所有