一、题目内容

image.png

二、题解

解法1：

思路

先转后缀，再计算

代码

  1. public class Solution {
  2.     /**
  3.      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  4.      * 返回表达式的值
  5.      * @param s string字符串 待计算的表达式
  6.      * @return int整型
  7.      */
  8.     public int solve (String s) {
  9.         // write code here
  10.         return eval(transToPostOrder(s));
  11.     }
  13.     private List<String> transToPostOrder(String s){
  14.         List<String> ans = new ArrayList<String>();
  15.         //优先级
  16.         HashMap<String, Integer> map = new HashMap<>();
  17.         map.put("+", 1);
  18.         map.put("-", 1);
  19.         map.put("*", 2);
  20.         map.put("/", 2);
  22.         Stack<String> stack = new Stack<String>();
  23.         int index = 0;
  24.         while (index < s.length()) {
  25.             String target = "";
  26.             if (!Character.isDigit(s.charAt(index))) {
  27.                 target = s.charAt(index) + "";
  28.                 index++;
  29.             } else {
  30.                 while (index < s.length() && Character.isDigit(s.charAt(index))) {
  31.                     target += s.charAt(index) + "";
  32.                     index++;
  33.                 }
  34.             }
  36.             if (!map.containsKey(target)) {
  37.                 if (target.equals("(")) {
  38.                     stack.push(target);
  39.                 } else if (target.equals(")")) {
  40.                     while (!stack.peek().equals("(")) {
  41.                         ans.add(stack.pop());
  42.                     }
  43.                     stack.pop();
  44.                 } else {
  45.                     ans.add(target);
  46.                 }
  47.             } else {
  48.                 if(stack.isEmpty()){
  49.                     stack.push(target);
  50.                 }else{
  51.                     String peek = stack.peek();
  52.                     while (!stack.isEmpty() && !peek.equals("(") && map.get(stack.peek()) > map.get(target)) {
  53.                         ans.add(stack.pop());
  54.                     }
  55.                     stack.push(target);
  56.                 }
  57.             }
  58.         }
  59.         while (!stack.isEmpty()) {
  60.             ans.add(stack.pop());
  61.         }
  62.         return ans;
  63.     }
  65.     private int eval(List<String> tokens){
  66.         Stack<Integer> stack = new Stack<Integer>();
  67.         for(String token: tokens){
  68.             if(isNumber(token)){
  69.                 stack.push(Integer.parseInt(token));
  70.             }else{
  71.                 Integer num2 = stack.pop();
  72.                 Integer num1 = stack.pop();
  73.                 switch (token) {
  74.                     case "+":
  75.                         stack.push(num1 + num2);
  76.                         break;
  77.                     case "-":
  78.                         stack.push(num1 - num2);
  79.                         break;
  80.                     case "*":
  81.                         stack.push(num1 * num2);
  82.                         break;
  83.                     case "/":
  84.                         stack.push(num1 / num2);
  85.                         break;
  86.                     default:
  87.                 }
  88.             }
  89.         }
  90.         return stack.pop();
  91.     }
  93.     public boolean isNumber(String token) {
  94.         return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
  95.     }
  96. }