leetcode 224. Basic Calculator | 224. 基本计算器（中缀表达式求值）

梦里梦外; 2022-09-11 03:22 140阅读 0赞

## 题目 ##

[https://leetcode.com/problems/basic-calculator/][https_leetcode.com_problems_basic-calculator]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

## 题解 ##

中缀表达式求值，之前学数据结构的笔记：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

class Solution { 
        public int calculate(String s) { 
            if (s.trim().startsWith("-")) s = "0" + s;
            
            Stack<Integer> numStack = new Stack<>();
            Stack<Character> opStack = new Stack<>();
            int cur = 0;
            boolean pending = false;
            for (char c : s.toCharArray()) { 
                if (c == ' ') { 
                    // pass
                } else if (c == '(') { 
                    if (pending) { 
                        numStack.push(cur);
                        cur = 0;
                        pending = false;
                    }
                    opStack.push(c);
                } else if (c == ')') { 
                    if (pending) { 
                        numStack.push(cur);
                        cur = 0;
                        pending = false;
                    }
                    char op = opStack.pop();
                    while (op != '(') { 
                        int b = numStack.pop();
                        int a = numStack.pop();
                        numStack.push(cal(a, b, op));
                        op = opStack.pop();
                    }
                } else if (c >= '0' && c <= '9') { 
                    cur *= 10;
                    cur += c - '0';
                    pending = true;
                } else { 
                    if (pending) { 
                        numStack.push(cur);
                        cur = 0;
                        pending = false;
                    }
                    if (!opStack.isEmpty() && opStack.peek() != '(') { 
                        char op = opStack.pop();
                        int b = numStack.pop();
                        int a = numStack.pop();
                        numStack.push(cal(a, b, op));
                    }
                    opStack.push(c);
                }
            }
            if (pending) { 
                numStack.push(cur);
            }
            if (!opStack.isEmpty()) { 
                char op = opStack.pop();
                int b = numStack.pop();
                int a = numStack.pop();
                numStack.push(cal(a, b, op));
            }
            return numStack.pop();
        }
    
        public int cal(int a, int b, char op) { 
            return op == '+' ? a + b : a - b;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

[https_leetcode.com_problems_basic-calculator]: https://leetcode.com/problems/basic-calculator/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/684b50e406904986a6e32165ce9274f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220828/ea49a11508414dc48d79f143039d739f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220828/834feb5c474e4f8d9d13b3f86db66f63.png