What is an infix expression? What is a postfix expression?

The operators of infix expressions are in the middle of operands in infix form. Infix expressions are common arithmetic representations such as :(3 + 4) * 5-8/2

Postfix expressions, also called inverse Polish expressions, are expressions of the form 3, 4 + 5 * 8, 2 / – : the operator comes after the operand, and prefix expressions: the operator precedes the operand.

Why do we have infix expressions and postfix expressions?

Because infix expression is easy for us to understand and calculate, but suffix expression is more convenient for computer operation (such as binary tree, stack, etc.), so after reading an infix expression, we convert it into suffix expression, and then hand over to the computer operation will be more convenient.

The realization of suffixes from infix

  • The first step is to define two stacks as a numeric stack and a symbolic stack
  • We split the entire expression to get each operand and operator
  • Iterate over the split array:
  1. If the string is a value, if it is, it is pushed onto the value stack.
  2. If the string is), if it is, it means that the data in the parentheses needs to be converted, and the two top elements in the numeric stack and the top elements in the symbolic stack are taken out in turn, spliced together, separated by Spaces in the middle, and then pressed into the numeric stack.
  3. If the string is (, it is pushed directly into the symbol stack.
  4. If the string is other symbols (+, -, *, /), judge that if the symbol stack is not empty, then compare the priority of the symbol on the top of the stack with that of the symbol. If the priority of the element on the top of the stack is high, then repeat the conversion splicing operation in 2. If the symbol stack is empty, it is pushed directly into the symbol stack.
  5. Repeat steps 1, 2, 3, and 4 until the traversal is complete.
  • If the symbol stack is empty, the final result (i.e. the unique element in the value stack) is printed directly, otherwise the operation of 2 above is repeated.

Code Implementation (Java)

import java.util.Stack;

public class transform {
    public static void main(String[] args) {
        Stack<String> stack_value = new Stack<>();
        Stack<String> stack_symbol = new Stack<>();
        String expression = "3 plus 4 times 5-8/2";
        String [] str = expression.split("");
        for (String s:str
             ) {
            if (isValue(s)) {
                stack_value.push(s);
            } else {
                if (s.equals(")")) {
                    Intermediate_results(stack_value, stack_symbol);
                    stack_symbol.pop();
                } else if (s.equals("(")) {
                    stack_symbol.push(s);
                } else {
                    if(! stack_symbol.isEmpty()) {if(priority(s) <= priority(stack_symbol.peek())) { Intermediate_results(stack_value, stack_symbol); } } stack_symbol.push(s); }}}while(! stack_symbol.isEmpty()) { Intermediate_results(stack_value, stack_symbol); } System.out.println(stack_value.peek()); }// Check if it is a numeric value, return true for a numeric value
    public static Boolean isValue (String s) {
        return! s.equals("+") && !s.equals("-") && !s.equals("*") && !s.equals("/") && !s.equals("(") && !s.equals(")");
    }
    
    // Calculate the priority of each operator
    public static int priority(String s) {
        int p = 0;
        switch (s) {
            case "+":
            case "-": {
                p = 1;
                break;
            }

            case "*":
            case "/": {
                p = 2;
                break;
            }
            case "(": {
                p = -1;
                break; }}return p;
    }

    // Add and push intermediate results
    public static void Intermediate_results(Stack<String> stack_value, Stack<String> stack_symbol) {
        String res = "";
        String s2 = stack_value.pop();
        String s1 = stack_value.pop();
        res += s1 + "" + s2;
        res += ""+ stack_symbol.pop(); stack_value.push(res); }}Copy the code