Šetnja kroz grad

Jovan je šetao gradom po mreži ulica. Kreće se samo u četiri smera:

• L — jednu ulicu levo
• R — jednu ulicu desno
• U — jednu ulicu gore
• D — jednu ulicu dole

Ponekad se predomisli pa se vrati nazad istim putem:

• B — vraćanje jedne ulice unazad

Jovan je dovoljno pametan da ne pravi kružne putanje tokom svoje šetnje, ali često se desi se istim ulicama vrati nazad.

Pomogni Joanu da odredi najkraći redosled koraka koji opisuje njegovu šetnju od početne do krajnje tačke.

Opis ulaza

Sa standardnog ulaza se učitava niska \(S\) dužine \(n\) (\(0 < n < 10^5\)) koju čine karakteri L, R, U, D, i B.

Opis izlaza

Na standardni izlaz ispisati nisku najkraćeg niza koraka koja zaista opisuje njegovu putanju.

Primer 1

Ulaz

LRRUUBD

Izlaz

R

Objašnjenje

• LR se poništavaju (ostaje RUUBD).
• Drugo U i B se brišu (ostaje RUD).
• U i D se poništavaju (ostaje R).

Primer 2

Ulaz

UDLRLDBRBDU

Izlaz

Rešenje

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

bool are_opposite(char a, char b) {
    return (a == 'L' && b == 'R') || (a == 'R' && b == 'L') ||
           (a == 'U' && b == 'D') || (a == 'D' && b == 'U');
}

int main() 
{
    string str; cin >> str;

    stack<char> s;
    for (char c : str) {
        if (c == 'B') {
            if (!s.empty()) s.pop();
        } else if (!s.empty() && are_opposite(s.top(), c)) {
            s.pop();
        } else {
            s.push(c);
        }
    }

    string res;
    while (!s.empty()) {
        res.push_back(s.top());
        s.pop();
    }
    reverse(res.begin(), res.end());

    cout << res << endl;

    return 0;
}