补全左括号-白红宇

补全左括号

阅读量：4352 次

发布时间：2019-06-07

本文共 3725 字，大约阅读时间需要 12 分钟。

问题：

编写一道程序，从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式。例如，给定输入：1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )你的程序应该输出：((1 + 2) * ((3 - 4) * (5 - 6)))

解：

　　1 + 2）应该变成（1+2），这里的操作数是1和2，运算符是+，这里的逻辑是 "操作数1+运算符+操作数2+）" 应该变成"（操作数1+运算符+操作数2+）"。。。意思就是如果（1+2）*（3-4）），这里的操作数分别是（1+2）和（3-4），运算符是*，这是基本思路。

　　这里使用两个栈，一个data栈存储操作数，一个op栈存储运算符，当 "操作数1+运算符+操作数2+） =>（操作数1+运算符+操作数2+）"这一个操作完成后"（操作数1+运算符+操作数2+）"将作为一个操作数存储在data栈中。

完整代码：

public class test {    static void rank(String a){        Stack
     
       op = new Stack
      
       ();        Stack
       
         data = new Stack
        
         ();        for (int i = 0; i < a.length(); i++ ){            if(isNum(a.charAt(i))){                //如果是数字                data.push(String.valueOf(a.charAt(i)));            }            if(isOp(a.charAt(i))){                //如果是运算符                op.push(String.valueOf(a.charAt(i)));            }            if(a.charAt(i) == ')'){                //如果是右括号                String d1 = data.pop();                String d2 = data.pop();                String ops = op.pop();                data.push("(" + d2 + ops + d1 + ")");            }        }        //打印结果        System.out.println(popAllStack(data));    }    //递归实现将整个栈连接成一个String    static String popAllStack( Stack
         
           stack){        String result = stack.pop();        if(stack.empty()){            return result;        }        return result + popAllStack(stack);    }    //判断是一个数    static Boolean isNum(char a){        if(a >= '0' && a <= '9'){            return true;        }        return false;    }    //判断是一个运算符    static Boolean isOp(char a){        if ("+-*/".indexOf(String.valueOf(a)) != -1){            return true;        }        return false;    }    public static void main(String[] args) {        String a = "1+2)*3-4)*5-6)))";        rank(a);    }}

问题1：1+2)*3-4)*5-6)))为什么不能是(((1+2)*(3-4)*5-6)))，，不过这个不重要，强行把题目变得简单而已。。

问题2：数字是多位怎么办，比如122+332)*3-4)*5-6)))，修改一下操作数进栈的部分即可，修改思路是：122+332）* 166+233 一个数字的结束后会接上一个运算符、右括号或者字符串结束。

public class test {    static void rank(String a){        Stack
     
       op = new Stack
      
       ();        Stack
       
         data = new Stack
        
         ();        String num = "";        for (int i = 0; i < a.length(); i++ ){            if(isNum(a.charAt(i))){                //如果是数字                num = num + a.charAt(i);                System.out.println(num);                if(a.charAt(i + 1) == ')' || isOp(a.charAt(i + 1))) {                    data.push(num);                    num = "";                }            }            if(isOp(a.charAt(i))){                //如果是运算符                op.push(String.valueOf(a.charAt(i)));            }            if(a.charAt(i) == ')'){                //如果是右括号                String d1 = data.pop();                String d2 = data.pop();                String ops = op.pop();                data.push("(" + d2 + ops + d1 + ")");            }        }        //打印结果        System.out.println(popAllStack(data));    }    //递归实现将整个栈连接成一个String    static String popAllStack( Stack
         
           stack){        String result = stack.pop();        if(stack.empty()){            return result;        }        return result + popAllStack(stack);    }    //判断是一个数    static Boolean isNum(char a){        if(a >= '0' && a <= '9'){            return true;        }        return false;    }    //判断是一个运算符    static Boolean isOp(char a){        if ("+-*/".indexOf(String.valueOf(a)) != -1){            return true;        }        return false;    }    public static void main(String[] args) {        String a = "12+2)*3-4)*5-6898)))";        rank(a);    }}

转载于:https://www.cnblogs.com/xxbbtt/p/8176954.html

你可能感兴趣的文章