抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

逆波兰表达式算法-Java版

这两天一直在看数据结构,栈这个地方,基础的就是这个逆波兰表达式,看了很多博文,都讲得不清不楚或者只能计算一个位的数字,决定自己写,这篇博文给了很大启发–>Go New Land AND Here

逆波兰简而言之是将中缀转换为后缀表达式,从而方便计算机进行四则运算,属于栈的基本运用

操作符优先级: ()    +-     */%(从左到右递增)

规则:

1.建立一个OP(操作栈),一个ArrayList(存储输出结果)

2.将字符串从左向右遍历,把数据放入ArrayList,把运算符压入运算符的栈

  关于运算符压栈的规则:

⑴ 如果OP为空或者为待压栈操作符为左括号则直接将运算符压入栈

⑵ 如果待压栈操作符的优先级大于栈顶操作符则直接入栈

⑶ 如果待压栈操作符的优先级小于栈顶操作符,则将OP栈顶的操作符依次输出 直到遇到左括号或者OP为空则停止,此时压入该操作符到OP栈顶中

⑷ 如果遇到右括号则将OP栈中的元素依次弹出 输出 直到遇到左括号为止,同时弹出左括号不放入ArrayList,并且右括号不压入OP

⑸ 最后将OP中的元素依次弹出输出, 将ArrayList输出则是最终的逆波兰表达式

JAVA代码:

import java.util.ArrayList; import java.util.Stack; 
/**  * 将中缀表达式转出后缀表达式,再计算其结果  * 中缀表达式 9+(3-1)*3+10/2 = 20 转后缀931-3*+10 2/+  */ 
public class 栈逆波兰表达式 {  
    public static void toOpArray(String x) {  
        //存储输出的结果  
        ArrayList operate =new ArrayList();  
        //操作符的栈  
        Stack stack = new Stack();  
        //原始串  
        StringBuffer oldString=new StringBuffer();  
        char[] old = (x + " ").toCharArray();  
        StringBuffer stringBuffer = new StringBuffer();  
        for (char read : old) {  
            //原始操作符分割 数字和操作符的区分  
            if (read >= 48 && read <= 57) {  
                stringBuffer.append(read);  continue;  
            } else {  
                if (stringBuffer.length() != 0) {  
                    //存入数字操作符分隔好的原始表达式  
                    oldString.append(stringBuffer+" ");  
                    operate.add(Integer.valueOf(stringBuffer.toString()));  stringBuffer.setLength(0);  
                }  
            }  
            //最后的空格不参与计算  
            if (read==' '){  
                continue;  
            }    
            //存入数字操作符分隔好的原始表达式  
            oldString.append(read+" ");  
            //解析 OP为操作栈  
            //⑴ 如果OP为空或者为待压栈操作符为左括号则直接将运算符压入栈  
            if (stack.isEmpty()||read=='('){  
                stack.push(read);  
                //结束此次运算符操作  
                continue;  
            }  
            //⑷ 如果遇到右括号则将OP栈中的元素依次弹出 输出至operate中直到遇到左括号为止,弹出左括号但不输出至operate 并且右括号不压入OP  
            if (read==')'){  
                //不为空则一直循环  
                while (!stack.isEmpty()){  
                    char tmp= (char) stack.pop();  
                    //当遇到左括号 弹出并结束循环  
                    if (tmp=='('){  
                        break;  
                    }  
                    //否则输出到operate中  
                    operate.add(tmp);  
                }  
                continue;  
            }  
            //普通情况  
            if (!stack.isEmpty()){  
                char top= (char) stack.pop();  
                int readPri=getPriority(read);  
                int topPri=getPriority(top);  
                //⑵ 如果待压栈操作符的优先级大于栈顶操作符则直接入栈  
                if (readPri>topPri){  
                    //不要忘记将弹出的压入  
                    stack.push(top);  
                    stack.push(read);  
                }else {  
                    //⑶ 如果栈顶操作符的优先级大于待压栈操作符,则将OP栈顶的操作符依次输出  
                    // 直到遇到左括号或者OP为空则停止,此时压入该操作符到OP栈顶中  
                    operate.add(top);  
                    while (true){  
                        if (!stack.isEmpty()){  
                            char tmp= (char) stack.pop();  
                            if (tmp=='('){  
                                stack.push(tmp);  
                                break;  
                            }  
                            operate.add(tmp);  
                        }else {  
                            break;  
                        }  
                    }  
                    stack.push(read);  
                }  
            }  
        }  
        //⑸ 最后将OP中的元素依次弹出并输出,则operate为最终的逆波兰表达式  
        while (!stack.isEmpty()){  
            operate.add(stack.pop());  
        }  
        //输出  
        System.out.println("原始串:"+oldString);  
        System.out.print("结果串:");  
        for (int i = 0; i < operate.size(); i++) {  
            System.out.print(operate.get(i) + " ");  
        }  
        //计算结果  
        //getRes(operate);  
        System.out.println("\n");  
    }  
    //() +- */ 优先级从小到大  
    public static int getPriority(char read) {  
        int pri = -1;  
        switch (read) {  
            case '+':  pri = 1;  break;  
            case '-':  pri = 1;  break;  
            case '*':  pri = 2;  break;  
            case '/':  pri = 2;  break;  
            case '(':  pri = 0;  break;  
            case ')':  pri = 0;  break;
          }  
          return pri;
        }  
        public static void main(String[] args) {  
            System.out.println("理论串:"+"9 3 1 - 3 * + 10 2 / +");  
            toOpArray("90+(3-1)*3+10/2");  
            toOpArray("9+10/2+(3-1)*3");  
            toOpArray("10/2+(3-1)*3+90");  
        } 
    } 
    //计算结果
    private static void getRes(ArrayList operate) {  
        Stack stack=new Stack();  
        //因为我上面的逆波兰最后面带了一个空格 所以最后一个元素为空 不计算 这里减一  
        for (int i = 0; i <operate.size()-1 ; i++) {  
            if (operate.get(i).equals('+')||operate.get(i).equals('-')
            ||operate.get(i).equals('*')||operate.get(i).equals('/')){  
                //操作符处理  
                char c= (char) operate.get(i);  
                int b= (int) stack.pop();  
                int a= (int) stack.pop();  
                switch (c){  
                    case '+':  stack.push(a+b);  break;  
                    case '-':  stack.push(a-b);  break;  
                    case '*':  stack.push(a*b);  break;  
                    case '/':  stack.push(a/b);  break;  
                }  
            }  else {  
                //数字压栈  
                stack.push(operate.get(i));  
            }  
        }  
        System.out.println("结果为:"+stack.pop());  
        System.out.println(); 
    }

看了规则,写一遍代码,就可以理解了。

当然,我这个也没处理负数,没处理被除数为0的情况

大概思路:

负数:当遇到一个操作符() + – * / 第二次如果依旧为操作字符而且为-时 下个数字做负数处理

被除数为0:遇到/后,判断下个数字是否为0,为0则抛出异常

发现一个bug:

(24*1+(4+6)*2) + (4-3*2)*(4+6-9+(11-3*4)*2+2)*10+20-3*2*4+2 会是1738
(24*1+(4+6)*2) 是44
(4-3*2)*(4+6-9+(11-3*4)*2+2)*10+20-3*2*4+2 是-22
 
 没能找到原因,待高手指点。

0条评论

发表评论