Baekjoon 2800

25 May 2024 in Study / Computer science on Baekjoon 2800

Stack

Description

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(23, ((2+3)4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(22)+2)에서 괄호를 제거하면, (2+22+2), 2+(22)+2, 2+22+2를 만들 수 있다. 하지만, (2+22)+2와 2+(22+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

Input

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, ‘+’, ‘*’, ‘-‘, ‘/’, ‘(‘, ‘)’로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다.

Output

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

Example I & O

Input
(0/(0))

Output
(0/0)
0/(0)
0/0

Input
(2+(2*2)+2)

Output
(2+22+2)
2+(22)+2
2+2*2+2

Input
(1+(2*(3+4)))

Output
(1+(23+4))
(1+2(3+4))
(1+23+4)
1+(2(3+4))
1+(23+4)
1+2(3+4)
1+2*3+4

My solution

typedef struct stack
{
    int Capacity;
    int Top;
    char* data;
} Stack;

typedef struct stack2
{
    int Capacity;
    int Top;
    int* data;
} Stack2;

void createStack(Stack** charStack, int capacity)
{
    *charStack = (Stack*)malloc(sizeof(Stack));
    (*charStack)->data = (char*)malloc(sizeof(char) * (capacity + 1));
    (*charStack)->Capacity = capacity;
    (*charStack)->Top = -1;

}

void createStack2(Stack2** intStack, int capacity)
{
    *intStack = (Stack2*)malloc(sizeof(Stack2));
    (*intStack)->data = (int*)malloc(sizeof(int) * (capacity + 1));
    (*intStack)->Capacity = capacity;
    (*intStack)->Top = -1;
}

void deleteStack(Stack** charStack)
{
    free((*charStack)->data);
    (*charStack)->data = NULL;
    free(*charStack);
    *charStack = NULL;
}

void deleteStack2(Stack2** intStack)
{
    free((*intStack)->data);
    (*intStack)->data = NULL;
    free(*intStack);
    *intStack = NULL;
}

void push(Stack* charStack, char datum)
{
    charStack->Top++;
    charStack->data[charStack->Top] = datum;
}

void push2(Stack2* intStack, int datum)
{
    intStack->Top++;
    intStack->data[intStack->Top] = datum;
}

char pop(Stack* charStack)
{
    char topDatum = charStack->data[charStack->Top];
    charStack->Top--;

    return topDatum;
}

int pop2(Stack2* intStack)
{
    int topDatum = intStack->data[intStack->Top];
    intStack->Top--;

    return topDatum;
}

int countParenthesis(char* data)
{
  int count = 0;

  for(int i = 0; i < strlen(data); i++)
  {
    char datum = data[i];
    if datum == '('                                    //)
      count++;
  }
  return count;
}

int compare(const void* a, const void* b)
{
    return strcmp(*(char**)a, *(char**) b);
}


int main()
{
    char notation[201];
    memset(notation, 0, sizeof(notation));
    Stack* operatorStack = NULL;
    Stack2* parenthesisStack = NULL;


    scanf("%s", notation);

    int length = strlen(notation);
    int n = countParenthesis(notation);
    createStack(&operatorStack, length);
    createStack2(&parenthesisStack, 11);

    int sizeofArray = pow(2, n);

    char** resultArray = (char**)malloc(sizeof(char*) * sizeofArray);
    for (int i = 0; i < sizeofArray; i++)
    {
        resultArray[i] = (char*)malloc(sizeof(char) * 201);
    }

    int lengthResult = 0;

    for (int i = 1; i < pow(2, n); i++)
    {
        char resultString[201];
        memset(resultString, 0, sizeof(resultString));
        int numberLeftParenthesis = 0;
        int numberRightParenthesis = 0;

        for (int j = 0; j < strlen(notation); j++)
        {
            char currentChar = notation[j];
            if (currentChar == '(')
            {
                numberLeftParenthesis++;
                push2(parenthesisStack, numberLeftParenthesis);
                if (i & (1 << (n - numberLeftParenthesis)))
                {
                    continue;
                }
                else
                {
                    push(operatorStack, currentChar);
                }
            }
            else if (currentChar == ')')
            {
                numberRightParenthesis = pop2(parenthesisStack);

                if (i & (1 << n - numberRightParenthesis))
                {
                    continue;
                }
                else
                {
                    push(operatorStack, currentChar);
                }
            }
            else
            {
                push(operatorStack, currentChar);
            }
        }

        int resultLength = operatorStack->Top;
        for (int k = 0; k < resultLength + 1; k++)
        {
            resultString[resultLength - k] = pop(operatorStack);
        }

        strcpy(resultArray[lengthResult], resultString);
        lengthResult++;

    }

    qsort(resultArray, lengthResult, sizeof(char*), compare);


    for (int i = 0; i < lengthResult; i++)
    {
        if (i >= 1 && strcmp(resultArray[i-1], resultArray[i]) == 0)
            continue;
        else
        {
            printf("%s\n", resultArray[i]);
        }
    }

    deleteStack(&operatorStack);
    deleteStack2(&parenthesisStack);
    for (int i = 0; i < sizeofArray; i++)
    {
        free(resultArray[i]);
        resultArray[i] = NULL;
    }
    free(resultArray);
    resultArray = NULL;

    return 0;
}

Sketch
- We need to find how we check all parenthesis pairs’ combinations that gonna be removed
  - 1^st : Given the notation and during doing linear search for all cases, we need to identify each parenthesis pairs (assign the number : “numberLeftParenthesis” for left parenthesis & “ numberRightParenthesis” for right parenthesis)
    - For assigning the number to each parenthesis, we need to use Stack
    - While doing linear search (-> This gonna be second “for” statement) for given notation, we just add 1 to numberLeftParenthesis everytime we meet the left parenthesis
    - After this, current numberLeftParenthesis has to enter the stack (parenthesisStack : This stack is for finding the numberRightParenthesis for current right parenthesis)
    - If we meet the right parenthesis from linear search, this right parenthesis’ number (numberRightParenthesis) gonna be the top value of parenthesisStack
    - Through this process, we can identify all parenthesis pairs
  - 2^nd : We need to use Combination Search with bit operation
    - This is a matter of whether certain parenthesis gonna be chosen or not like bit (1 or 0)
    - If we let n be the number of parenthesis pairs
      - for (int i = 1; i < pow(2, n); i++) : Through this, we can check all cases for possible combinations -> This gonna be first “for” statement
      - ex) Given n = 3 and if current i is 5
        i = 5 = 4 + 1 = 2² + 2⁰
        I made a rule by connecting the possible case with bit pattern (It is ok for this rule to be different)
        Because of n=3, there are parenthesis pair 0, parenthesis pair 1, and parenthesis pair 2
        For i = 5 case, it means I gonna remove parenthesis pair 0 & parenthesis pair 2 by my rule
    - If current charater is the thing except the parenthesis, we just put it into the stack (operatorStack) for making one result string
    - if (i & (1 « (n - numberLeftorRightParenthesis))) : If current parenthesis is true for this “if” statement, we just pass because this parenthesis need to remove
- We need to sort the array having notations resulted from removing the parenthesis pairs with passing the duplicated data
Code Analysis

typedef struct stack
{
    int Capacity;
    int Top;
    char* data;
} Stack;

typedef struct stack2
{
    int Capacity;
    int Top;
    int* data;
} Stack2;

void createStack(Stack** charStack, int capacity)
{
    *charStack = (Stack*)malloc(sizeof(Stack));
    (*charStack)->data = (char*)malloc(sizeof(char) * (capacity + 1));
    (*charStack)->Capacity = capacity;
    (*charStack)->Top = -1;

}

void createStack2(Stack2** intStack, int capacity)
{
    *intStack = (Stack2*)malloc(sizeof(Stack2));
    (*intStack)->data = (int*)malloc(sizeof(int) * (capacity + 1));
    (*intStack)->Capacity = capacity;
    (*intStack)->Top = -1;
}

void deleteStack(Stack** charStack)
{
    free((*charStack)->data);
    (*charStack)->data = NULL;
    free(*charStack);
    *charStack = NULL;
}

void deleteStack2(Stack2** intStack)
{
    free((*intStack)->data);
    (*intStack)->data = NULL;
    free(*intStack);
    *intStack = NULL;
}

void push(Stack* charStack, char datum)
{
    charStack->Top++;
    charStack->data[charStack->Top] = datum;
}

void push2(Stack2* intStack, int datum)
{
    intStack->Top++;
    intStack->data[intStack->Top] = datum;
}

char pop(Stack* charStack)
{
    char topDatum = charStack->data[charStack->Top];
    charStack->Top--;

    return topDatum;
}

int pop2(Stack2* intStack)
{
    int topDatum = intStack->data[intStack->Top];
    intStack->Top--;

    return topDatum;
}

I prepared 2 types stack for string (operatorStack) and integer data (parenthesisStack)

int countParenthesis(char* data)
{
    int count = 0;

    for (int i = 0; i < strlen(data); i++)
    {
        char datum = data[i];
        if (datum == '(')                     /)
            count++;
    }

    return count;
}

This is for finding the number of the parenthesis pairs

int compare(const void* a, const void* b)
{
    return strcmp(*(char**)a, *(char**) b);
}

int compare(const void* a, const void* b)
{
    return strcmp((char*)a, (char*)b);
}

This is for using qsort from stdlib.h
compare function
String a == String b -> 0
String a > String b -> > 0
String a < String b -> < 0
If the array (need to sort) of string is char array[][], we need to use second version of compare function If the array of string is char** array (dynamic assignment), we need to use first version of compare function

//main

char notation[201];
memset(notation, 0, sizeof(notation));
Stack* operatorStack = NULL;
Stack2* parenthesisStack = NULL;

scanf("%s", notation);

int length = strlen(notation);
int n = countParenthesis(notation);
createStack(&operatorStack, length);
createStack2(&parenthesisStack, 11);

int sizeofArray = pow(2, n);

char** resultArray = (char**)malloc(sizeof(char*) * sizeofArray);
for (int i = 0; i < sizeofArray; i++)
{
    resultArray[i] = (char*)malloc(sizeof(char) * 201);
}

int lengthResult = 0;

input : notation (Use memset for initialization of notation)
n : the number of the parenthesis pairs
pow(2, n) : the size of resultArray (the array having notations resulted from removing the parenthesis pairs)
Initialization of resultArray : Dynamic assignment
lengthResult : current index for resultArray + After finishing the linear search, it gonna be the final length of resultArray

//main

for (int i = 1; i < pow(2, n); i++)
    {
        char resultString[201];
        memset(resultString, 0, sizeof(resultString));
        int numberLeftParenthesis = 0;
        int numberRightParenthesis = 0;

        //
    }

resultString : For current i (one possible combination), final string

//main

char notation[201];
memset(notation, 0, sizeof(notation));
Stack* operatorStack = NULL;
Stack2* parenthesisStack = NULL;

scanf("%s", notation);

int length = strlen(notation);
int n = countParenthesis(notation);
createStack(&operatorStack, length);
createStack2(&parenthesisStack, 11);

int sizeofArray = pow(2, n);

char** resultArray = (char**)malloc(sizeof(char*) * sizeofArray);
for (int i = 0; i < sizeofArray; i++)
{
    resultArray[i] = (char*)malloc(sizeof(char) * 201);
}

int lengthResult = 0;

//main

for (int i = 1; i < pow(2, n); i++)
    {
        //

        for (int j = 0; j < strlen(notation); j++)
        {
            char currentChar = notation[j];
            if (currentChar == '(')
            {
                numberLeftParenthesis++;
                push2(parenthesisStack, numberLeftParenthesis);
                if (i & (1 << (n - numberLeftParenthesis)))
                {
                    continue;
                }
                else
                {
                    push(operatorStack, currentChar);
                }
            }
            else if (currentChar == ')')
            {
                numberRightParenthesis = pop2(parenthesisStack);

                if (i & (1 << n - numberRightParenthesis))
                {
                    continue;
                }
                else
                {
                    push(operatorStack, currentChar);
                }
            }
            else
            {
                push(operatorStack, currentChar);
            }
        }
    }

For current i (current possible combination), we need to do linear search for given notation
If current character is the thing except the parenthesis, we just put it into operatorStack (Its elements gonna be collected for resultString)
If current character is (, its number (ID) is previous numberLeftParenthesis + 1. Plus, its id gonna enter parenthesisStack for identifying what is one right parenthesis’ id
If current left parenthesis’ id makes the condition be true, it won’t enter operatorStack
If current character is ), its number (ID) is top of parenthesisStack
If current right parenthesis’ id makes the condition be true, it won’t enter operatorStack

//main

for (int i = 1; i < pow(2, n); i++)
    {
        //

        //

        int resultLength = operatorStack->Top;
        for (int k = 0; k < resultLength + 1; k++)
        {
            resultString[resultLength - k] = pop(operatorStack);
        }

        strcpy(resultArray[lengthResult], resultString);
        lengthResult++;
    }

Getting the element out of operatorStack and it enter resultString one by one with backward direction
Final resultString is stored to resultArray at current index (lengthResult)

//main

qsort(resultArray, lengthResult, sizeof(char*), compare);


for (int i = 0; i < lengthResult; i++)
{
    if (i >= 1 && strcmp(resultArray[i-1], resultArray[i]) == 0)
        continue;
    else
    {
        printf("%s\n", resultArray[i]);
    }
}


deleteStack(&operatorStack);
deleteStack2(&parenthesisStack);
for (int i = 0; i < sizeofArray; i++)
{
    free(resultArray[i]);
    resultArray[i] = NULL;
}
free(resultArray);
resultArray = NULL;

return 0;

qsort : sorting resultArray
qsort(array, current number of elements in array, a element’s byte, compare)
A element’s byte : integer element -> sizeof(int), char[20][30] -> sizeof(char) x 30, char** -> sizeof(1 dimension pointer of char)
strcmp(resultArray[i-1], resultArray[i]) == 0 -> pass (remove the duplicated data)
Comparison of string has to be done with strcmp

Baekjoon 2800

Description

Input

Output

Example I & O

My solution

Bioinformatics

Error

Description

Input

Output

Example I & O

My solution

Templates (for web app):

Error