7-line O(N) C++ solution using stack scanning backward (detailed explanation)

  • 0

    Key observation: Ternary expression is defined as grouping from right to left, so the sub-expression of first '?' from right is always calculated first.

    Simply using a stack<char> chars to scan string expression from right to left:

    1. if encounter a non '?' char, just push it into stack;
    2. if encounter a '?' at index i, e.g., in string fraction "...T?5:8...", we must have
      • char at next index i-1 expression[i-1] = 'T' is the condition char;
      • char at top of stack chars.top = '5' is the first value in current ternary expression;
      • char at 3rd top of stack '8' is the second value in current ternary expression.
        Then we just pop out those chars, calculate the current ternary expression and push the result back to stack.
    3. continue to next char in expression til its begining.
    4. The final result must be the single char in the stack.
        string parseTernary(string expression) {
          stack<char> chars; 
          for (auto i = expression.rbegin(); i != expression.rend(); ++i)
            if (*i == '?') { // calculate ternary expression
              char TF = *(++i), first = chars.top(), second = (chars.pop(),chars.pop(),chars.top()); 
              chars.pop(); chars.push(TF == 'T'? first : second); // push result back into stack
            } else chars.push(*i); // push other chars into stack
          return string(1, chars.top());

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.