2 C++ solutions : forward & backward parsing, stores stack in the problem input (Both in 9ms)


  • 0

    Really interesting to find out there are 2 ways to deal with this problem.
    At first I didn't see it says "no sapce in the input string", so I took care of it. :P

    class Solution {
    public:
        string parseTernary(string expression) {
    #if 1 // forward parsing
            int idx = -1;
            for(const auto& ch : expression) {
                if(ch == '?' || ch == 'T' || ch == 'F' || ch>='0' && ch <= '9') expression[++idx] = ch;
                else {
                    while(idx-4 >= 0 && expression[idx-1] == ':') {
                        idx -= 4;
                        if(expression[idx] == 'T')expression[idx] = expression[idx+2];
                        else expression[idx] = expression[idx+4];
                    }
                    expression[++idx] = ch;
                }
            }
            while(idx-4 >= 0) {
                idx -= 4;
                if(expression[idx] == 'T')expression[idx] = expression[idx+2];
                else expression[idx] = expression[idx+4];
            }
            return {expression[0]};
    #else //backward parsing
            int idx = expression.size();
            for(int i = idx-1;i>=0;--i) {
                char ch = expression[i];
                if(ch == '?' || ch>='0' && ch <= '9') expression[--idx] = ch;
                else if(ch == 'T' || ch == 'F') {
                    if(idx+2 < expression.size() && expression[idx] == '?') {
                        idx+=2;
                        if(ch == 'T') expression[idx] = expression[idx-1];
                    } else {
                        expression[--idx] = ch;
                    }
                }
            }
            return {expression.back()};
    #endif
        }
    };
    

Log in to reply
 

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