14.java 中缀表达式转后缀表达式

思路如下：

1、初始化两个栈，运算符栈和中间结果栈

2、从左至右扫描

3、遇到数时直接压入s2

4、遇到运算符时，比较其与s1栈顶的优先级，有如下几种情况：

1）s1为空或栈顶为“（”或此运算符优先级大于s1栈顶符优先级时，直接入栈

2）s1栈顶运算符优先级大于等于该运算符时，不断从s1栈中弹出栈顶并压入s2直到s1为空或优先级大于s1栈顶。然后将此运算符压入s1

5、遇到括号时：

1）为左括号则直接压入s2

2）为右扩号时则不断弹出s1栈顶压入s2直到遇到左括号时，停止弹出并将这一对括号丢弃

6、扫描到最右边时结束循环

7、将s1中的运算符依次弹出并压入s2

8、依次弹出s2中的元素并输出，结果的逆序则为后缀表达式。

主要依赖两个方法，

1、将中缀表达式分割转换为一个list

需要考虑多位数，遍历字符串s，不是数字则直接add入list，是数字则进入while循环直到结束或得到的后一位不为数字了结束拼接，add入list刚刚得到的拼接字符串

public static List<String> tolist(String s){

        List<String> list=new ArrayList<String>();

        String str="";

        char ch=' ';

        int i=0;

        do {

            if((s.charAt(i)<48)||(s.charAt(i)>57)){

                list.add(""+s.charAt(i));

                i++;

            }else {

                str="";

                while (i<s.length()&&s.charAt(i)>=48&&s.charAt(i)<=57){

                    str+=s.charAt(i);

                    i++;

                }

                list.add(str);

            }

        }while (i<s.length());

        return list;

    }

2、将分割后的list转换为后缀表达式

定义两个栈，但由于s2没有pop的操作且之后还要倒序输出所以这里以list来代替栈。遍历list，依据上述描述来写逻辑。

public static List<String> parseList(List<String> list){

        Stack<String> stack=new Stack<String>();

        List<String> ls=new ArrayList<String>();

        for (String item:list){

            if(item.matches("\\d+")){

                ls.add(item);

            }else if (item.equals("(")){

                stack.push(item);

            }else if (item.equals(")")){

                while (stack.size()!=0&&!stack.peek().equals("(")){

                    ls.add(stack.pop());

                }

                stack.pop();

            }else {

                while (stack.size()!=0&&oper.getvalue(stack.peek())>=oper.getvalue(item)){

                    ls.add(stack.pop());

                }

                stack.push(item);

            }

        }

        while (stack.size()!=0){

            ls.add(stack.pop());

        }

        return ls;

    }

巴特西

14.java 中缀表达式转后缀表达式

最新文章

热门文章