Как оценить нотацию обратной полировки с использованием стеков

Да, оно может.

S = new empty stack
while not eof
    t = read token
    if t is a binary operator
        y = pop(S)
        x = pop(S)
        push(S, t(x, y))
    else
        push(S, t)
print the contents of the stack S

Просто переберите весь массив и:

• push каждого number, которого вы встретите, в стек
• если вы встретите operation token - pop два числа из стека и оцените операцию
• push результат вашей операции обратно в стек

Вот и все. Сложность для этого будет linear, O(n) по времени и linear, O(n) по пространству, потому что мы используем стек для хранения чисел. Весь код с использованием стека (JavaScript):

/*
  Function to perform operation with two numbers.
  @param {String} Operation type.
  @param {Number} Number 1.
  @param {Number} Number 2.
  @returns {Number} Result of performing the operation.
*/
var performOperation = function performOperation(operation, num1, num2) {
    switch (operation) {
        case '+': return num1 + num2;
        case '-': return num1 - num2;
        case '*': return ~~(num1 * num2);
        case '/': return ~~(num1 / num2);
        default: console.error('Unknown operation: ', operation);
    }
};
/*
  Function to check if variable holds an operation type.
  @param {Any} Token.
  @returns {Boolean} If token is string with operation type.
*/
var isOperation = function isNumber(token) {
    // map of supported operations
    var map = {
        '+': true,
        '-': true,
        '*': true,
        '/': true
    }
    return !!map[token];
};

var evaluatePolishNotation = function evaluatePolishNotation(tokens) {
  var stack = [];
  for (var i = 0; i < tokens.length; i++) {
    var token = tokens[i];
    if (isOperation(token)) {
      var number1 = stack.pop();
      var number2 = stack.pop();
      stack.push( performOperation(token, number2, number1) );
    } else {
      stack.push( parseInt(tokens[i], 10) );
    }
  }
  return stack.pop();
}

Но вы можете улучшить это, используя постоянное пространство O(1)! Узнайте больше об алгоритме здесь.