스택 활용

스택의 대표적인 활용으로 수식의 괄호 쌍, 전위/중위/후위 표기법, DFS, Flood fill등이 존재한다.

 

수식의 괄호 쌍?

주어진 괄호 문자열이 올바른지 판단하는 문제이다.

• 여는 괄호가 나올 시 스택에 추가
• 닫는 괄호가 나올 시,
  • 스택이 비어있으면 올바르지 않은 괄호 쌍
  • 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍
  • 스택의 top이 짝이 맞는 괄호일 경우 pop
• 모든 과정을 마친 후 스택에 남아있는 요소가 있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍

연습 문제

 

1. 백준 4949 : https://www.acmicpc.net/problem/4949

 

while(true)
{
    var input = Console.ReadLine();

    if (input == ".") break;
    Stack<char> stack = new Stack<char>();
    bool isValid = true;

    foreach(var s in input)
    {
        if(s == '(' || s == '[') stack.Push(s);
        else if (s == ')')
        {
            if(stack.Count == 0 || stack.Peek() != '(')
            {
                isValid = false;
                break;
            }
            stack.Pop();
        }
        else if (s == ']')
        {
            if (stack.Count == 0 || stack.Peek() != '[')
            {
                isValid = false;
                break;
            }
            stack.Pop();
        }
    }
    if(stack.Count > 0) isValid = false;
    if (isValid) Console.WriteLine("yes");
    else Console.WriteLine("no");
}

 

 

2. 백준 10799 : https://www.acmicpc.net/problem/10799

var input = Console.ReadLine();
Stack<char> stack = new Stack<char>();
var answer = 0;
char prev = default;
foreach(var s in input)
{
    if (s == '(') stack.Push(s);
    else if (s==')')
    {
        stack.Pop();
        if(prev == '(')
        {
            answer += stack.Count;
        }
        else if (prev == ')')
        {
            answer++;
        }
    }
    prev = s;
}
Console.WriteLine(answer);

 

 

3. 백준 2504 : https://www.acmicpc.net/problem/2504

와 첫 골드 문제라 그런지 3시간은 붙잡고 있던 것 같다

var input = Console.ReadLine();
Stack<AAAA> stack = new Stack<AAAA>();
int answer = 0;

if (input == null)
    return;

foreach (var s in input)
{

    if (s == '(' || s == '[') { stack.Push(new AAAA(s, 0)); }
    else if (s == ')')
    {
        if (stack.Count == 0 || stack.Peek().c != '(') { answer = 0; break; } 
        else
        {
            var a = stack.Pop();
            if (stack.Count > 0)
            {
                if (a.i > 0)
                {
                    var temp = stack.Pop();
                    temp.i += a.i * 2;
                    stack.Push(temp);
                }
                else
                {
                    var temp = stack.Pop();
                    temp.i += 2;
                    stack.Push(temp);
                }
            }
            else
            {
                if (a.i > 0) answer += a.i * 2;
                else answer += 2;
            }
        }
    }
    else if (s == ']')
    {
        if (stack.Count == 0 || stack.Peek().c == '(') { answer = 0; break; }
        else
        {
            var a = stack.Pop();
            if(stack.Count > 0)
            {
                if(a.i > 0)
                {
                    var temp = stack.Pop();
                    temp.i += a.i * 3;
                    stack.Push(temp);
                }
                else
                {
                    var temp = stack.Pop();
                    temp.i += 3;
                    stack.Push(temp);
                }
            }
            else
            {
                if (a.i > 0) answer += a.i * 3;
                else answer += 3;
            }
        }
    }
}
if (stack.Count != 0) answer = 0;
Console.WriteLine(answer);


struct AAAA
{
    public char c;
    public int i;

    public AAAA(char c, int i)
    {
        this.c = c;
        this.i = i;
    }
}

string input = Console.ReadLine();
int temp = 1; int answer = 0;
Stack<char> stack = new Stack<char>();
Action<int, bool> Cal = (n, b) => {
    if(b) answer += temp;
    temp /= n;
    stack.Pop();
};
for(int i =0; i < input.Length; i++)
{
    if(input[i] == '('){
        temp *= 2;
        stack.Push('(');
    }
    else if (input[i] == '['){
        temp *= 3;
        stack.Push('[');
    }
    else if(input[i] == ')'){
        if (stack.Count == 0 || stack.Peek() != '(') { answer = 0; break; }
        else if (input[i - 1] == '(') Cal(2, true);
        else Cal(2, false);
    }
    else if (input[i] == ']'){
        if (stack.Count == 0 || stack.Peek() != '[') { answer = 0; break; }
        else if (input[i - 1] == '[') Cal(3, true);
        else Cal(3, false);
    }
}
if (stack.Count != 0) answer = 0;
Console.WriteLine(answer);