中缀表达式转后缀表达式

这里仅讨论包含+ - * / ()的中缀表达式,并且没有对表达式合法性进行校验.

顺序遍历所给中缀表达式串的每个字符:

1. 若是数字,直接输出
2. 若是符号,分情况讨论.
   通常是当前符号比栈顶符号优先级高时,当前符号才入栈.(优先级相同时仍是先出栈后压栈,因为同优先级计算方式是顺序的,从左到右)
   +和-优先级最低,只有栈为空或者栈顶符号是左括号(时才入栈;
   乘和除优先级高一些,栈为空或者栈顶不是* 和/号时入栈.
   左括号(直接入栈.
   若是右括号),则不断出栈直到遇上左括号(. 将左括号(也出栈,注意右括号不入栈

例 KS34

代码参考Java版

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String s = scan.nextLine();
        // 中缀表达式转后缀
        List<String> res = ParseStr(s);
        // 计算后缀表达式的值
        int ans = getValue(res);
        System.out.println(ans);
    }
    private static List<String>ParseStr(String s){
        Stack<String>stack = new Stack<>();
        List<String>list = new ArrayList<>();
        for(int i=0;i<s.length();++i){
            String tmp = String.valueOf(s.charAt(i));
            switch(tmp){
                case "+":
                case "-":
                    // 加减号只有栈为空或者栈顶是'('才能入栈
                    while(!stack.empty()&& !stack.peek().equals("("))
                        list.add(stack.pop());
                    stack.push(tmp);
                    break;
                case "*":
                case "/":
                    // 乘除号在栈空或者栈顶不为乘除号时入栈
                    while(!stack.empty()&& (stack.peek().equals("*")||stack.peek().equals("/")))
                        list.add(stack.pop());
                    stack.push(tmp);
                    break;
                case "(":
                    // 左括号直接入栈
                    stack.push(tmp);
                    break;
                case ")":
                    // 若是右括号,不断出栈直到遇到左括号.将左括号也出栈, 注意这里右括号不入栈
                    while(!stack.empty()&& !stack.peek().equals("("))
                        list.add(stack.pop());
                    stack.pop();
                    break;

                // 数字
                default:
                    int sum = Integer.parseInt(tmp);
                    while(i+1<s.length()&&s.charAt(i+1)<='9'&&s.charAt(i+1)>='0')
                    {
                        sum = sum * 10 + (s.charAt(i+1)-'0');
                        ++i;
                    }
                    list.add(String.valueOf(sum));
            }
        }
        while(!stack.empty())
            list.add(stack.pop());
        return list;
    }
    // 后缀表达式计算:遇到操作符,从栈顶弹出两个操作数进行计算.注意操作数的先后顺序.将计算完的结果压栈.
    // 反复进行,直到最后栈内剩下一个元素. 就是计算结果
    private static int getValue(List<String>list){
        Stack<Integer>stack = new Stack<>();
        for(String s:list){
           switch(s){
               case "+":
                   stack.push(stack.pop()+stack.pop());
                   break;
               case "-":
                   int b = stack.pop();
                   int a = stack.pop();
                   stack.push(a-b);
                   break;
               case "*":
                   stack.push(stack.pop()*stack.pop());
                   break;
               case "/":
                   int b1 = stack.pop();
                   int a1 = stack.pop();
                   stack.push(a1/b1);
                   break;
               default:
                   stack.push(Integer.parseInt(s));

           }
        }
        return stack.pop();
    }
}