题解 | #表达式求值#

表达式求值

http://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4

两个栈 st1st2,一个用来存操作数 (st1) ,一个用来存运算符和左括号 (st2)

  1. 当遇到 '(' 就入 st2 栈。
  2. 当遇到操作数就如 st1 栈。
  3. 当遇到操作符,有两种情况
    3.1 如果这个操作符优先级小于等于 st2 栈顶操作符的优先级,则从 st1 中出栈两个操作数,从 st2 中出栈一个操作符,并做运算,将运算结果放入 st1 栈中。
    3.2 如果这个操作符优先级大于 st2 栈顶操作符的优先级,则直接入栈。
  4. 当遇到 ')' ,每次出栈两个操作数和一个操作符,并将运算结果存入 st1 中,直到 st2 栈顶为 '(' ,并将这个 '(' 出栈。


public class Solution {
    
    public int solve (String s) {
        // write code here
        Map<Character, Integer> priority = new HashMap<>();
        priority.put('+', 1);
        priority.put('-', 1);
        priority.put('*', 2);
        Deque<Integer> stack1 = new LinkedList<>(); // 存放操作数
        Deque<Character> stack2 = new LinkedList<>(); // 存放运算符和左括号
        s = "(" + s + ")"; // 这样可以使结束后栈中仅剩的一个数就是结果
        int i = 0;
        while(i < s.length()){
            char ch = s.charAt(i);
            if(ch == '('){
                stack2.push(ch);
            }else if(ch - '0' >= 0 && ch - '0' <= 9){
                int num = 0;
                // 累加操作数
                while(Character.isDigit(s.charAt(i))){
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                i--;
                stack1.push(num);
            }else if(ch == '+' || ch == '-' || ch == '*'){
                if(!stack2.isEmpty() && priority.containsKey(stack2.peek()) && priority.get(ch) <= priority.get(stack2.peek())){
                    int b = stack1.pop();
                    int a = stack1.pop();
                    char op = stack2.pop();
                    int c = operation(a, op, b);
                    stack1.push(c);
                }
                stack2.push(ch);
            }else{
                while(!stack2.isEmpty() && stack2.peek() != '('){
                    int b = stack1.pop();
                    int a = stack1.pop();
                    char op = stack2.pop();
                    int c = operation(a, op, b);
                    stack1.push(c);
                }
                stack2.pop();
            }
            i++;
        }
        return stack1.pop();
    }
    
    private int operation(int a, char op, int b){
        if(op == '+') return a + b;
        if(op == '-') return a - b;
        if(op == '*') return a * b;
        return a / b;
    }
}
全部评论

相关推荐

05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
昨天 16:13
嘉应学院 Python
xiaolihuam...:很明显骗子,如果是hr直接约你面试了,哪用得着内推,如果是员工的话,你得多优秀,一线员工直接加你微信,
点赞 评论 收藏
分享
评论
5
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务