使用栈完成后缀表达式求和

短命女 2023-02-12 05:53 12阅读 0赞

# 例子 #

例题1  
中缀表达式“8+4-6\*2” = 0  
后缀表达式表示为：8 4 + 6 2 \* -

例题2  
中缀表达式：（70 + 30） \*20 + 10 / 2 - 3 = 2002  
后缀表达式： 70 30 + 20 \* 10 2 / + 3 -

例题3  
中缀表达式： 10 \* 3 +（3-1）\* 2 - 10 / 2 = 29  
后缀表达式：10 3 \* 3 1 - 2 \* + 10 2 / -

例题3：  
中缀表达式“2\*(3+5)+7/1-4 = 19  
后缀表达式表示为：3 5 + 2 \* 7 1 /4 - +

注意：当前没有小数点，只有加减乘除

# 题目解析 #

从前向后扫描：

*  遇到数字，入栈
 *  遇到符号，弹出两个数，然后计算（栈底的元素在前，栈顶的元素在后面），将计算的结果入栈

public static String back_cal(String [] strs){
        
            Stack<String> stack = new Stack<>();
    
            for (int i = 0; i < strs.length; i++){
        
                if (isNumeric(strs[i])){
        
                    stack.push(strs[i]);
                    continue;
                }
    
                if (stack.size() < 2){
        
                    throw new RuntimeException("非法的表达式:");
                }
                stack.push(cal(stack.pop(), stack.pop(), strs[i]));
            }
    
            if (stack.empty()){
        
                throw new RuntimeException("非法的表达式:");
            }
    
            return stack.pop();
        }
    
        public static boolean isNumeric(String str) {
        
            String bigStr;
            try {
        
                bigStr = new BigDecimal(str).toString();
            } catch (Exception e) {
        
                return false;//异常 说明包含非数字。
            }
            return true;
        }
    
        public static int stringToint(String str){
        
            return Integer.parseInt(str);
        }
        public static String cal(String top, String button, String oper){
        
            int t = stringToint(top);
            int b = stringToint(button);
    
            switch (oper){
        
                case "+":
                    return String.valueOf(b + t);
                case "-":
                    return String.valueOf(b - t);
                case "/":
                    return String.valueOf(b / t);
                case "*":
                    return String.valueOf(b * t);
                default:
                    throw new RuntimeException("错误的符号");
            }
        }
    
        public static void main(String[] args) {
        
    
            System.out.println(back_cal(new String[]{
        "10", "3", "*", "3", "1", "-", "2", "*", "+", "10", "2", "/", "-"}));
            System.out.println(back_cal(new String[]{
        "8", "4", "+", "6", "2", "*", "-"}));
            System.out.println(back_cal(new String[]{
        "70", "30", "+", "20", "*", "10", "2", "/", "+", "3", "-"}));
        }