package exp5;

//---------------------------------------------------------------
//  MyBC.java   Author: 唐才铭   Date：2018-06-13
//
//  实现中缀表达式转后缀表达式的功能。
//---------------------------------------------------------------

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class MyBC {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String another = "y";
        while (another.equalsIgnoreCase("y"))  //  allows y or Y
        {
            System.out.print("请输入中缀表达式：");
            String infix = scanner.nextLine();
            System.out.print("输入的中缀表达式转换成后缀表达式为：");
            String suffix = infixToSuffix(infix);
            System.out.print(suffix);
            System.out.println();
            System.out.print("是否继续 (y/n)?");
            another = scanner.nextLine();
        }
    }

    // 将中缀表达式转换为后缀表达式
    public static String infixToSuffix(String exp) {
        // 创建操作符堆栈
        List<String> Operator_stack = new LinkedList<>();
        Stack<Character> s = new Stack<Character>();
        // 要输出的后缀表达式字符串
        String suffix = "";
        String[] A = exp.split(" ");
        int length = exp.length() ; // 输入的中缀表达式的长度
        for (int i = 0; i < length; i++) {
            char temp;// 临时字符变量
            // 获取该中缀表达式的每一个字符并进行判断
            char ch = exp.charAt(i);
            switch (ch) {
                // 忽略空格
                case ' ':
                    break;
                // 如果是左括号直接压入堆栈
                case '(':
                    s.push(ch);
                    Operator_stack.add(s.toString());
                    break;

                // 碰到'+' '-'，将栈中的所有运算符全部弹出去，直至碰到左括号为止，输出到队列中去
                case '+':
                case '-':
                    while (s.size() != 0) {
                        temp = s.pop();
                        Operator_stack.add(s.toString());
                        if (temp == '(') {
                            // 重新将左括号放回堆栈，终止循环
                            s.push('(');
                            Operator_stack.add(s.toString());
                            break;
                        }
                        suffix += temp+ " ";
                    }
                    // 没有进入循环说明是当前为第一次进入或者其他前面运算都有括号等情况导致栈已经为空,此时需要将符号进栈
                    s.push(ch);
                    Operator_stack.add(s.toString());
                    break;

                // 如果是乘号或者除号，则弹出所有序列，直到碰到加好、减号、左括号为止，最后将该操作符压入堆栈
                case '*':
                case '/':
                    while (s.size() != 0) {
                        temp = s.pop();

                        Operator_stack.add(s.toString());
                        // 只有比当前优先级高的或者相等的才会弹出到输出队列，遇到加减左括号，直接停止当前循环
                        if (temp == '+' || temp == '-' || temp == '(') {
                            s.push(temp);
                            Operator_stack.add(s.toString());
                            break;
                        }
                        else {
                            suffix += temp + " ";
                        }
                    }
                    // 没有进入循环说明是当前为第一次进入或者其他前面运算都有括号等情况导致栈已经为空,此时需要将符号进栈
                    s.push(ch);
                    Operator_stack.add(s.toString());
                    break;

                // 如果碰到的是右括号，则距离栈顶的第一个左括号上面的所有运算符弹出栈并抛弃左括号
                case ')':
                    // 这里假设一定会遇到左括号了，此为自己改进版，已经验证可以过
                    // while ((temp = s.pop()) != '(') {
                    // suffix += temp;
                    // }
                    while (!s.isEmpty()) {
                        temp = s.pop();
                        Operator_stack.add(s.toString());
                        if (temp == '(') {
                            break;
                        } else {
                            suffix += temp+ " ";
                        }
                    }
                    break;
                // 默认情况，如果读取到的是数字，则直接送至输出序列
                default:
                    suffix += ch+ " ";
                    break;
            }
        }
        // 如果堆栈不为空，则把剩余运算符一次弹出，送至输出序列
        while (s.size() != 0) {
            suffix += s.pop()+ " ";
            Operator_stack.add(s.toString());
        }
        return suffix;
    }
}