后序表达式转化为中序表达式

一.后序表达式转化为中序表达式

后序表达式 2 3 * 2 1 - / 3 4 1 - * +  

中序表达式 ( ( ( 2 * 3 ) / ( 2 - 1 ) ) + ( 3 * ( 4 - 1 ) ) )

我们在学习数据结构的时候就知道需要用到栈

通过观察不难发现我们在后序表达式中每次遇到“+”，“-”，“*”，“/”时都要处理对应的前2个数，例如2 3 *

处理为（ 2 * 3 ）此时 （ 2 * 3 ）就变成了一个数 可以供后面的符号处理。

这样一来我们的思路变清晰了：

即每次遇到“+”，“-”，“*”，“/”符号 就对前2个数作处理，处理后将得到的数压人栈中

如我们遇到的是数则直接压人栈中即可

因为我们是表达式转化 没有必要声明栈为double 或int的 String就可以了

我们只需要声明一个String型的名为val（val代表数值）栈

Stack val = new Stack();就可以了

然后对后序表达式的输入做如下处理

while(!StdIn.isEmpty()){ //当输入不为空时String s = StdIn.readString();if(s.equals("+")){ //输入为加号String v = val.pop();//里符号最近的数v=String.format("( %s %s %s )",val.pop(),s,v); //对里符号最近的2个数最处理 例如 2 3 +  v=（ 2 +3 ） val.push(v); //将处理后的数v=（ 2+ 3）压人栈 下面3个都一样}else if(s.equals("-")){String v = val.pop();v=String.format("( %s %s %s )",val.pop(),s,v);val.push(v);}else if(s.equals("*")){String v = val.pop();v=String.format("( %s %s %s )",val.pop(),s,v);val.push(v);}else if(s.equals("/")){String v = val.pop();v=String.format("( %s %s %s )",val.pop(),s,v);val.push(v);}else  //如果是数值，直接压人栈val.push(s);}

最后 

StdOut.println(val.pop()); //此时val栈中只有一个元素了

结果

二.中序表达式的求值

 ( ( ( 2 * 3 ) / ( 2 - 1 ) ) + ( 3 * ( 4 - 1 ) ) )

思路和上面差不多  我采用的是Dijkstar双栈法

声明2个栈 一个为String型的ops（符号）栈 另一个是Double型的val（数值）栈

Stack val =  new Stack<>();
Stack ops = new Stack<>();

对上面的中序表达式从左到右依次处理

遇到“(” 我们不管 因为“(”有嵌套，我们不知道什么时候该处理

遇到数值将它压人val栈中

遇到“+”，“-”，“*”，“/”时将它压人ops栈中

遇到“)”时我们开始处理 因为一个“)”代表一个子表达式的介绍这时 我们取出第一个数 value=val.pop() 和符号ops.pop()

并令value = value +val.pop() 再把value压人val栈中 val.push(value)    注意符号是从ops中取出来的 

在中序表达式没有结束前依次重复上面操作

最后val栈中只剩下一个数 这个数就是结果 

代码如下

import edu.princeton.cs.algs4.*;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;public class Evaluate {public static void main (String [] args){Stack val =  new Stack<>();Stack ops = new Stack<>();while(!StdIn.isEmpty()){String s = StdIn.readString();if(s.equals("("));else if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")) ops.push(s);else if(s.equals(")")){String op = ops.pop();double v = val.pop();if(op.equals("+")) v=val.pop()+v;else if(op.equals("-")) v=val.pop()-v;else if(op.equals("*")) v = val.pop()*v;else if(op.equals("/")) v = val.pop()/v;val.push(v);}elseval.push(Double.parseDouble(s));}StdOut.println(val.pop());}
}

结果

溜了溜了

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！