mayoko’s diary

プロコンとかいろいろ。

SRM 521 div1 easy: MissingParentheses

SRM 521 の練習会に参加しました。もうちょっとで med も解けそうだったんですか残念ながら easy だけしか通してないです。

解法

'(' と ')' の対応を見るためにスタックで管理するだけ。

class MissingParentheses {
public:
    int countCorrections(string par) {
        stack<char> st;
        int n = par.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (par[i] == ')') {
                if (st.empty() || st.top() == ')') ans++;
                else st.pop();
            } else {
                st.push(par[i]);
            }
        }
        ans += st.size();
        return ans;
    }
};