150. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9

["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

150. Вычисление обратной польской записи

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

Возможные операторы: +, -, *, /. Каждый операнд представляет собой число или другое арифметическое выражение.

Примеры:

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9

["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

// C++

class Solution {

public:

int evalRPN(vector<string>& tokens) {

}

};

// Java

public class Solution {

public int evalRPN(String[] tokens) {

}

}

РЕШЕНИЕ

структуры данных - стек

Анализ алгоритма

Обрабатываем последовательно токены. Объявим стек, который в начале работы пустой.

· Если токен является числом, то занесем его в стек.

· Если токен – арифметическая операция, то извлечем из стека два последних числа, выполним над ними операцию и занесем в стек результат.

После окончания обработки всех токенов на вершине стека находится результат.

Реализация алгоритма

class Solution

{

public:

int evalRPN(vector<string>& tokens)

{

stack<int> s;

if (tokens.size() == 0) return 0;

string op = "+-*/";

for(int i = 0; i < tokens.size(); i++)

{

string tok = tokens[i];

int o = op.find(tok);

if (o == -1)

s.push(atoi(tok.c_str()));

else

{

int a = s.top(); s.pop();

int b = s.top(); s.pop();

if (o == 0) s.push(b+a);

if (o == 1) s.push(b-a);

if (o == 2) s.push(b*a);

if (o == 3) s.push(b/a);

}

}

return s.top();

}

};

Java реализация

class Solution

{

public int evalRPN(String[] tokens)

{

if (tokens.length == 0) return 0;

Stack<Integer> s = new Stack<Integer>();

String operators = "+-*/";

for(int i = 0; i < tokens.length; i++)

{

String tok = tokens[i];

if (!operators.contains(tok))

s.push(Integer.valueOf(tok));

else

{

int a = s.peek(); s.pop();

int b = s.peek(); s.pop();

if (tok.equals("+")) s.push(b+a);

if (tok.equals("-")) s.push(b-a);

if (tok.equals("*")) s.push(b*a);

if (tok.equals("/")) s.push(b/a);

}

}

return s.peek();

}

}