中序、前序、后序表达式

1.中序表达式

中序表达式对我们而言是很直观的（我们平时接触的就是这个），但计算机处理起来比较麻烦（括号、优先级之类的），如2*3/(2-1)+3*(4-1)。前序和后序表达式中没有括号，而且在计算中只需单向扫描，不需要考虑运算符的优先级。

2.前序表达式

前序表达式就是前缀表达式，不含括号的算术表达式，而且它是将运算符写在前面，操作数写在后面的表达式，也称为“波兰式”。

2.1优点

前序表达式是一种十分有用的表达式，它将中序表达式转换为可以依靠简单的操作就能得到运算结果的表达式。例如，(a+b)*(c+d)转换为*,+,a,b,+,c,d。它的优势在于只用两种简单的操作，入栈和出栈就可以解决任何中序表达式的运算。其运算方式为：如果当前字符(或字符串)为数字或变量，则压入栈内；如果是运算符，则将栈顶两个元素弹出栈外并作相应运算，再将结果压入栈内。当前序表达式扫描结束时，栈里的就是中序表达式运算的最终结果。

2.2如何求值

对于一个前序表达式的求值而言，首先要从右至左扫描表达式，从右边第一个字符开始判断，如果当前字符是数字则一直到数字串的末尾再记录下来，如果是运算符，则将右边离得最近的两个“数字串”作相应的运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时，最后运算的值也就是表达式的值。例如，前序表达式“- 1 + 2 3“的求值，扫描到3时，记录下这个数字串，扫描到2时，记录下这个数字串，当扫描到+时，将+右移做相邻两数字串的运算符，记为2+3，结果为5，记录下这个新数字串，并继续向左扫描，扫描到1时，记录下这个数字串，扫描到-时，将-右移做相邻两数字串的运算符，记为1-5，结果为-4，所以表达式的值为-4。

2.3中序转前序例子

2.4中序转前序算法

1、反转输入字符串，如“2*3/(2-1)+3*(4-1)” 反转后为“ )1-4(*3+)1-2(/3*2”，
2、从字符串中取出下一个字符
　　2.1.如果是操作数，则直接输出
　　2.2.如果是“)”，压入栈中
　　2.3.如果是运算符但不是“(”，“)”,则不断循环进行以下处理
　　　　2.3.1.如果栈为空，则此运算符进栈，结束此步骤
　　　　2.3.2.如果栈顶是“)”,则此运算符进栈，结束此步骤
　　　　2.3.2.如果此运算符与栈顶优先级相同或者更高，此运算符进栈，结束此步骤
　　　　2.3.4.否则，运算符连续出栈输出，直到满足上述三个条件之一，然后此运算符进栈
　　2.4、如果是“(”，则运算符连续出栈输出，直到遇见“)”为止,将“)”出栈且丢弃之
3、如果还有更多的字符串，则转到第2步
4、不在有未处理的字符串了，输出栈中剩余元素
5、再次反转字符串得到最终结果

代码如下：

public class InfixToPrefix {
    public static void main(String[] args) {
        Stack<String> reverseStack = new Stack<String>();
        Stack<String> operatorStack = new Stack<String>();
        Stack<String> resultStack = new Stack<String>();
        while (!StdIn.isEmpty()) {
            String str = StdIn.readString();
            reverseStack.push(str);
        }
        while (!reverseStack.isEmpty()) {
            String str = reverseStack.pop();
            if (str.equals(")"))
                operatorStack.push(str);
            else if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
                boolean isEmpty;
                boolean isRightParen;
                boolean isHigherOperator;
                int i = 0;
                do {
                    if(i!=0){
                        resultStack.push(operatorStack.pop());
                    }
                    i++;
                    isEmpty = operatorStack.isEmpty();
                    isRightParen = false;
                    isHigherOperator = false;
                    if (!isEmpty) {
                        String stackTop = operatorStack.peek();
                        isRightParen = operatorStack.peek().equals(")");
                        if (stackTop.equals("+") || stackTop.equals("-")) {
                            isHigherOperator = true;
                        } else if ((stackTop.equals("*") || stackTop.equals("/"))
                                && (str.equals("*") || str.equals("/"))) {
                            isHigherOperator = true;
                        }
                    }
                    if(isEmpty||isRightParen||isHigherOperator){
                        operatorStack.push(str);
                        break;
                    }
                } while (!(isEmpty || isRightParen || isHigherOperator));
            }else if(str.equals("(")){
                String pop = operatorStack.pop();
                while(!pop.equals(")")){
                    resultStack.push(pop);
                    pop = operatorStack.pop();
                }
            }else{
                resultStack.push(str);
            }
        }
        for(String str:operatorStack){
            resultStack.push(str);
        }
        
        for(String str:resultStack){
            System.out.print(str);
        }
    }
}

3.后序表达式

后序表达式与前序表达式扫描方式正好相反

3.1中序转后序算法

1、当输入的是操作数时候，直接输出
2、当输入开括号时候，把它压栈
3、当输入的是闭括号时候，先判断栈是否为空，若为空，则发生错误并进行相关处理。若非空，把栈中元素依次出栈输出，直到遇到第一个开括号，若没有遇到开括号，也发生错误，进行相关处理
4、当输入是运算符op（+、- 、×、/）时候
a)循环，当（栈非空and栈顶不是开括号and栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作：将栈顶元素出栈输出
b)把输入的运算符op压栈
5、当中序表达式的符号序列全部读入后，若栈内仍有元素，把他们依次出栈输出。若弹出的元素遇到空括号，则说明不匹配，发生错误，并进行相关处理

代码如下：

public class InfixToPostfix {
    public static void main(String[] args) {
        Stack<String> operatorStack = new Stack<String>();
        while (!StdIn.isEmpty()) {
            String str = StdIn.readString();
            if (str.equals("("))
                operatorStack.push(str);
            else if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
                boolean isEmpty;
                boolean isLeftParen;
                boolean isLowerOperator;
                isEmpty = operatorStack.isEmpty();
                isLeftParen = false;
                isLowerOperator = false;
                if (!isEmpty) {
                    String stackTop = operatorStack.peek();
                    isLeftParen = operatorStack.peek().equals("(");
                    if ((stackTop.equals("+") || stackTop.equals("-")) && (str.equals("*") || str.equals("/"))) {
                        isLowerOperator = true;
                    }
                }
                if (!(isEmpty || isLeftParen || isLowerOperator)) {
                    for (int i = 0; i < operatorStack.size(); i++) {
                        StdOut.print(operatorStack.pop());
                    }
                }
                operatorStack.push(str);
            } else if (str.equals(")")) {
                String pop = operatorStack.pop();
                while (!pop.equals("(")) {
                    StdOut.print(pop);
                    pop = operatorStack.pop();
                }
            } else {
                StdOut.print(str);
            }
        }
        for (String str : operatorStack) {
            StdOut.print(str);
        }

    }
}