中缀转后缀

中缀表达式转后缀表达式

思路分析

将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式=>1 2 3 + 4 × + 5 -

步骤

1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2；

2. 从左至右扫描中缀表达式；

3. 遇到操作数时，将其压s2；

4. 遇到运算符时，比较其与s1栈顶运算符的优先级：

   1. 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

   2. 否则，若优先级比栈顶运算符的高，也将运算符压入s1；

   3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4. 1)与s1中新的栈顶运算符相比较；

5. 遇到括号时：

   1. 如果是左括号“(”，则直接压入s1

   2. 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃

6. 重复步骤2至5，直到表达式的最右边

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

8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

扫描到的元素	s2(栈底->栈顶)	s1 (栈底->栈顶)	说明
1	1	空	数字，直接入栈
+	1	+	s1为空，运算符直接入栈
(	1	+ (	左括号，直接入栈
(	1	+ ( (	同上
2	1 2	+ ( (	数字
+	1 2	+ ( ( +	s1栈顶为左括号，运算符直接入栈
3	1 2 3	+ ( ( +	数字
)	1 2 3 +	+ (	右括号，弹出运算符直至遇到左括号
×	1 2 3 +	+ ( ×	s1栈顶为左括号，运算符直接入栈
4	1 2 3 + 4	+ ( ×	数字
)	1 2 3 + 4 ×	+	右括号，弹出运算符直至遇到左括号
-	1 2 3 + 4 × +	-	-与+优先级相同，因此弹出+，再压入-
5	1 2 3 + 4 × + 5	-	数字
到达最右端	1 2 3 + 4 × + 5 -	空	s1中剩余的运算符

代码

主要方法

//讲中缀表达式转化为List
public static List<String> toInfixList ( String s ) {
    //先定义一个list,存放中缀表达式对应的内容
    List<String> ls=new ArrayList<String> (  ) ;
    int i = 0;//这是一个指针用于遍历中缀表达式字符串
    String str;//多位数拼接
    char c;//每遍历到一个字符就放入到c中
    do {
        //如果c是一个非数字，需要加到ls
        if ( (c=s.charAt ( i ))<48 ||(c=s.charAt ( i ))>57&&(c=s.charAt ( i ))!='.' ){  //ASCII表48-57是数字
            ls.add ( "" + c );
            i++;
        }else{
            str = "";//先将str置空
            while ((i<s.length ()&&((c=s.charAt ( i ))>=48&&(c=s.charAt ( i ))<=57)) ){
                str += c;//拼接
                i++;
            }
            ls.add ( str );

        }

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

    return ls;
}

//将得到的中缀表达式对应的List=>后缀对应的List
public static List<String> turnSuffixExpression ( List<String> ls ) {
    //定义两个栈
    Stack<String> s1 = new Stack<String> ( );
    //s2栈在整个过程没有弹出操作，又因为最后要逆序输出，所以使用ArrayList
    List<String> s2 = new ArrayList<String> ( );//用于存储中间结果

    //遍历ls
    for ( String i:ls ){
        //如果是一个数，加入s2
        if ( i.matches ( "\\d+" ) ) {
            s2.add ( i );
        }
        else if ( i.equals ( "(")) {
            s1.push ( i );
        }
        else if (i.equals ( ")" )){
            //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
            while (!s1.peek ( ).equals ( "(" )) {  //s1.peek()查看栈顶内容，但不弹出;如果栈顶没有到达（就不停止，继续弹
                s2.add ( s1.pop ( ) );
            }
            s1.pop ();//将（弹出s1,消除小括号
        }else {
            //若i优先级<=栈顶运算符将s1栈顶的运算符弹出并加入到s2中，再次转到（4.1）与s1中新的栈顶运算符相比较；
            //缺少比较一个运算符优先级高低的方法
            while (s1.size ()!=0&& Operation.getValue ( s1.peek () )>=Operation.getValue (  i)){
                s2.add ( s1.pop ( ) );
            }
            //// 比栈顶运算符的高，也将运算符压入s1；
            s1.push ( i );

        }
    }
    //将s1中剩下的运算符依次加入到s2中
    while (s1.size ( ) != 0) {
        s2.add ( s1.pop() );
    }

    //因为是存放到list中，正常输出即为后缀表达式
    return s2;
}

测试

public class PolandNotation {
    public static void main ( String[] args ) {

        //完成中缀表达式转后缀表达式
        //1. 1+（(2+3）*4）-5=>转成1 2 3 + 4 × + 5 -
        //2.因为直接对字符串操作不方便，所以我们先将1+（(2+3）*4）-5转成中缀的list
        //  即1+（(2+3）*4）-5转为【1，+，（，（，2，+，3，），*，4，），-，5】
        //3.将得到的中缀表达式对应的List=>后缀对应的List
        //即ArrayList【1，+，（，（，2，+，3，），*，4，），-，5】=>[]
        String expression = "1+((222+3)*4)-5";
        List<String> list = toInfixList ( expression );
        System.out.println ("中缀表达式List="+ list );
        List<String> suffixlist    = turnSuffixExpression ( list );
        System.out.println ( "后缀表达式List="+ suffixlist );
        }

    //讲中缀表达式转化为List
    public static List<String> toInfixList ( String s ) {
        //先定义一个list,存放中缀表达式对应的内容
        List<String> ls=new ArrayList<String> (  ) ;
        int i = 0;//这是一个指针用于遍历中缀表达式字符串
        String str;//多位数拼接
        char c;//每遍历到一个字符就放入到c中
        do {
            //如果c是一个非数字，需要加到ls
            if ( (c=s.charAt ( i ))<48 ||(c=s.charAt ( i ))>57&&(c=s.charAt ( i ))!='.' ){  //ASCII表48-57是数字
                ls.add ( "" + c );
                i++;
            }else{
                str = "";//先将str置空
                while ((i<s.length ()&&((c=s.charAt ( i ))>=48&&(c=s.charAt ( i ))<=57)) ){
                    str += c;//拼接
                    i++;
                }
                ls.add ( str );

            }

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

        return ls;
    }

    //将得到的中缀表达式对应的List=>后缀对应的List
    public static List<String> turnSuffixExpression ( List<String> ls ) {
        //定义两个栈
        Stack<String> s1 = new Stack<String> ( );
        //s2栈在整个过程没有弹出操作，又因为最后要逆序输出，所以使用ArrayList
        List<String> s2 = new ArrayList<String> ( );//用于存储中间结果

        //遍历ls
        for ( String i:ls ){
            //如果是一个数，加入s2
            if ( i.matches ( "\\d+" ) ) {
                s2.add ( i );
            }
            else if ( i.equals ( "(")) {
                s1.push ( i );
            }
            else if (i.equals ( ")" )){
                //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
                while (!s1.peek ( ).equals ( "(" )) {  //s1.peek()查看栈顶内容，但不弹出;如果栈顶没有到达（就不停止，继续弹
                    s2.add ( s1.pop ( ) );
                }
                s1.pop ();//将（弹出s1,消除小括号
            }else {
                //若i优先级<=栈顶运算符将s1栈顶的运算符弹出并加入到s2中，再次转到（4.1）与s1中新的栈顶运算符相比较；
                //缺少比较一个运算符优先级高低的方法
                while (s1.size ()!=0&& Operation.getValue ( s1.peek () )>=Operation.getValue (  i)){
                    s2.add ( s1.pop ( ) );
                }
                //// 比栈顶运算符的高，也将运算符压入s1；
                s1.push ( i );

            }
        }
        //将s1中剩下的运算符依次加入到s2中
        while (s1.size ( ) != 0) {
            s2.add ( s1.pop() );
        }

        //因为是存放到list中，正常输出即为后缀表达式
        return s2;
    }}

//编写一个Operation的类可以返回运算符优先级高低
class Operation{
    private static int ADD=1;
    private static int SUB=1;
    private static int MUL=2;
    private static int DIV=2;

    //写一个方法返回优先级数字
    public static int getValue ( String operation ) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD ;
                break;
            case "-":
                result = SUB ;
                break;
            case "*":
                result = MUL ;
                break;
            case "/":
                result = DIV ;
                break;
            default:
                System.out.println ("运算符有误" );
        }
        return result;
    }
}

结果