Evaluate Reverse Polish Notation
Medium About 15 min Free, no account needed
Evaluate a postfix expression - and get integer division right.
The brief
Given tokens in reverse Polish (postfix) notation with operators
+ - * /, return the value of the expression.
- Operands are integers; division truncates toward zero
(
6 / -132 == 0, not-1). - The expression is always valid.
The visible tests only divide positives. The hidden ones divide a positive by a
negative, if you compute the division in floating point and floor it, you get
-1 where the answer is 0. Use integer arithmetic on a stack of operands.
Starter code
using System;
using System.Collections.Generic;
public class Solution
{
// TODO: return the value of the postfix expression.
public long EvalRPN(string[] tokens)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Stacks
- Use last-in, first-out state for nesting, matching and expression evaluation.
Related katas
- Decode String Medium Free Expand k[encoded] patterns, nesting included.
- Simplify Unix Path Medium Free Canonicalize a Unix path - and survive the .. that climbs past root.
- Maximum Bracket Depth Easy Free How deep do the parentheses nest? A counter beats a stack.
- Roll Back the Payload Ledger Easy Free Track staged payload totals while nested checkpoints are opened and rolled back.