逆波兰式java

思路

从左到右遍历输入的中缀表达式，优先级*/大于+-。(最低，(不算到结果栈，设计2个栈，把输入的中缀表达式转换成字符数组，一个一个比较，经过下面的规则，最后得到了逆波式
1>遇到操作数，直接输出；
2>栈为空时，遇到运算符，入栈；
3>遇到左括号，将其入栈；
4>遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出；
5>遇到其他运算符’+”-”*”/’时，弹出所有优先级大于或等于该运算符的栈顶元素(即除了 ’ ( '，然后将该运算符入栈；
6>最终将栈中的元素依次出栈，输出。

举例

a*（b+c）-d/e
结果abc+*de/-

分析

程序流程图

package com.bo.chapter02;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class InversePolish {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        List<Character> symbol = new ArrayList<>();
        List<Character> result = new ArrayList<>();
        char[] input_char = input.toCharArray();//输入的式子
        int top = -1;//栈顶指针
        for (int i = 0; i < input_char.length; i++) {
            if (input_char[i] == '+' || input_char[i] == '-') {
                if (top == -1) {//栈空
                    symbol.add(input_char[i]);
                    top++;
                } else {
                    while (top > -1 && (symbol.get(top) != '(')) {//判断优先级
                        result.add(symbol.get(top));//出符号栈到输出栈
                        symbol.remove(top);//从符号栈移除掉
                        top--;
                    }
                    symbol.add(input_char[i]);//运算符入栈，加减优先级低
                    top++;
                }
            } else if (input_char[i] == '*' || input_char[i] == '/') {
                if (top == -1) {
                    symbol.add(input_char[i]);
                    top++;
                } else {
                    while ((symbol.get(top) != '(') && (symbol.get(top) == '*' || symbol.get(top) == '/')) {//*/优先级高，碰到/*会出栈
                        result.add(symbol.get(top));//出符号栈到输出栈
                        symbol.remove(top);//从符号栈移除掉
                        top--;
                    }
                    symbol.add(input_char[i]);
                    top++;
                }
            } else if (input_char[i] == '(') {
                symbol.add(input_char[i]);
                top++;
            } else if (input_char[i] == ')') {//)只要不遇到(之前的全部入结果栈
                while (symbol.get(top) != '(') {
                    result.add(symbol.get(top));//出符号栈到输出栈
                    symbol.remove(top);//从符号栈移除掉
                    top--;
                }
                symbol.remove(top);
                top--;//(出栈但是不算

            } else {//除了上述情况之外就是字母
                result.add(input_char[i]);
            }
        }
        //把整个字符数组判断完，把符号栈的全部放到结果栈里
        while (top > -1) {
            result.add(symbol.get(top));
            symbol.remove(top);
            top--;
        }

        System.out.println("逆波兰式：" + result.toString());
    }
}