目录

题目描述:

代码:

拓展:

中缀表达式转后缀表达式代码:

---

题目描述:

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

代码:

   public int evalRPN(String[] tokens){//数组长度是变化的
        LinkedList<Integer> stack = new LinkedList<>();//java自带的栈  容量自动变化
        for(String i:tokens){
            if(i.equals("+")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(a+b);
            }else if(i.equals("-")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b-a);
            }else if(i.equals("*")){
                int a = stack.pop();
                int b = stack.pop();
                stack.push(a*b);
            }else if(i.equals("/")){
                int a = stack.pop();//a
//                System.out.println(a);
                int b = stack.pop();//13
                System.out.println(b);
                stack.push(b/a);
            }else {
                stack.push(Integer.parseInt(i));//转换为int类型
            }
        }
        return stack.pop();
    }

拓展:

中缀表达式转后缀表达式代码:

package 表达式;

import java.util.LinkedList;

public class InfixToSuffix {
    // 中缀表达式转后缀表达式
    /* a+b   ab+
    *  a*b-c  ab*c-
    *  a+b*c   abc*+
    * 1.遇到非字符串,直接拼串
    * 2.遇到运算符  判断优先级，
    * 如果优先级高，则直接入栈，
    * 否则，>= 将栈内元素出栈，拼接 再入栈
    * 左括号直接入栈, 右括号把遇到左括号前的所有符号都出栈
    * 遍历完成,栈里剩余运算符 依次出栈拼接
    * */
    public static void main(String[] args) {
//        String exp = "a+b*c";
//        String exp = "1+2*3-4/5";
        String exp = "1+2*3-4/5*(6+7)";
        System.out.println(infixToSuffix(exp));

        }
    //判断优先级  +- 1  * / 2
    static int priority(char c) {
        switch(c){
            case '(':
                return 0;
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                return -1;
        }
    }
    // 中缀表达式转后缀表达式
    static String infixToSuffix(String exp){
        LinkedList<Character> stack = new LinkedList<>();
        StringBuilder sb = new StringBuilder(exp.length());
        for(int i=0;i<exp.length();i++){
            char c = exp.charAt(i);
            switch(c){
                case '+':
                case '-':
                case '*':
                case '/':{
                    if(stack.isEmpty()){//栈为空，直接入栈
                        stack.push(c);
                        break;
                    }else{
                        if(priority(c)>priority(stack.peek())) {//栈顶运算符优先级低
                            stack.push(c);
                            break;
                        }
                        else{
                            while(!stack.isEmpty()&&priority(c)<=priority(stack.peek())){//栈顶运算符优先级高或相等
                                sb.append(stack.pop());
                            }
                            stack.push(c);//通过前面对比,把优先级高或相等的先拼接,之后再把优先级低的运算符入栈
                            break;
                        }
                    }
                }
                case '(':
                    stack.push(c);
                    break;
                case ')':{
                    while(!stack.isEmpty()&&stack.peek()!='('){
                        sb.append(stack.pop());
                    }
                    stack.pop();//左括号弹出
                    break;
                }
                default:{
                    sb.append(c);
                    break;
                }
            }
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.toString();

    }
}