Литкод 150. Оцените Обратную Польскую Нотацию

Оцените значение арифметического выражения в обратной польской нотации.

Допустимыми операторами являются +, -, * и/. Каждый операнд может быть целым числом или другим выражением.

Обратите внимание, что деление между двумя целыми числами должно сокращаться до нуля.

Гарантируется, что данное выражение RPN всегда является действительным. Это означает, что выражение всегда будет приводить к результату, и не будет никакой операции деления на ноль.

Обратная польская нотация (RPN), также известная как польская постфиксная нотация или просто постфиксная нотация, представляет собой математическую нотацию, в которой операторы следуют за своими операндами, в отличие от польской нотации (PN), в которой операторы предшествуют своим операндам.

Пример 1:

Ввод: токены = [“2″,”1″,”+”,”3″,”*”] Вывод: 9 Объяснение: ((2 + 1) * Пример 2:

Ввод: токены = [“4″,”13″,”5″,”/”,”+”] Вывод: 6 Объяснение: (4 + (13/Пример 3:

Ввод: токены = [“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 + 5

• [“10″,”6″,”9″,”3″,”+”,”-11″,”
• “,”/”,”

Подход:

Подход довольно прост с использованием стека.

• Здесь всякий раз, когда мы видим цифру, мы просто помещаем ее в наш стек.

• Когда мы видим оператор + , мы просто вытаскиваем 2 верхних элемента, просто добавляем их и помещаем обратно в стек.

• Когда мы видим оператор * , мы просто вытаскиваем 2 верхних элемента, просто умножаем их и помещаем обратно в стек.

• Когда мы видим оператор - , нам нужно вывести 2 верхних элемента, но предположим, что b.pop() - первый элемент, который мы открываем и a.pop() - второй элемент, который мы вставляем и теперь мы разделяем а/б и подтолкните его обратно к нашей стопке.

• Когда мы видим оператор / , нам нужно вывести 2 верхних элемента, но предположим, что b.pop() - первый элемент, который мы открываем и a.pop() - второй элемент, который мы вставляем а теперь мы вычитаем a-b и помещаем его обратно в наш стек.

class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens.length == 0 || tokens == null)
            return -1;
        Stack stack = new Stack<>();
        for (String token : tokens) {
            if (token.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            }
            else if (token.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            }
            else if (token.equals("-")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a - b);
            }
            else if (token.equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a / b);
            }
            else {
                stack.push(Integer.valueOf(token));
            }
        }
        return stack.pop();
    }
}

O (длина Входного Массива) время и O (длина Входного Массива) пространство.

Ввод = [“10″,”6″,”9″,”3″,”+”,”-11″,” “,”/”,” “,”17″,”+”,”5″,”+”]

Rohith v 07/LeetCode топинтервью-вопросы

Основные вопросы для интервью Leetcode, обсуждаемые в Leetcode. Основные вопросы для интервью Leetcode, обсуждаемые в Leetcode.

Основные вопросы для интервью Leetcode, обсуждаемые в Leetcode. Основные вопросы для интервью Leetcode, обсуждаемые в Leetcode.

Также ответ на вопрос от CodeSignal.com: https://app.codesignal.com/

Rohithv07/Код доступа

Проблемы с LeetCode, которые решены.

Проблемы с LeetCode, которые решены.

Оригинал: “https://dev.to/rohithv07/150-evaluate-reverse-polish-notation-2pm5”