중위 표기식을 후위 표기식으로 변경해 주면 된다.
1. 스택에 자기 자신보다 높은 우선순위를 가진 연산자가 있으면 빼서 사용한다.
2. 스택에 입력된 연산자를 push 한다.
3. 괄호가 끝나면 사용하지 않은 연산자를 다 출력한다.
4. 남은 연산자들을 출력한다.
| BOJ 백준온라인져지 1261 알고스팟 풀이 Raw (0) | 2018.01.11 |
|---|---|
| BOJ 백준온라인져지 1504 특정한 최단 경로 풀이 (0) | 2018.01.09 |
| BOJ 백준온라인져지 1655 가운데를 말해요 풀이 (0) | 2018.01.06 |
| BOJ 백준온라인져지 1715 카드 정렬하기 풀이 (0) | 2018.01.04 |
| BOJ 백준온라인져지 11286 절대값 힙 풀이 (0) | 2018.01.02 |
| #include <cstdio> | |
| #include <stack> | |
| #include <vector> | |
| #include <string> | |
| #include <string.h> | |
| /** | |
| * https://www.acmicpc.net/problem/2504 | |
| * BOJ 백준온라인져지 2504 괄호의 값 풀이 | |
| */ | |
| using namespace std; | |
| int main(){ | |
| stack<char> characterList; | |
| int integerList[31] = {1}; // index 0 은 1 | |
| char temp, compared, pre = '.'; | |
| // temp 는 string 에서 하나씩 뽑아서 쓴다. | |
| // compared 는 ( or [ 가 들어가는데, 스택에서 빼서 쓴다. | |
| // pre 는 이전 괄호를 체크한다. 곱셈의 결합법칙에 의해 (()()) 일때 둘러싼 괄호는 0으로 처리해준다. | |
| char* string = new char[31]; // 입력 받을 string | |
| scanf("%s", string); | |
| int idx = 0, i = 0, length = strlen(string), tempInteger, result = 0; | |
| // idx 는 integerList에 접근하기 위한 변수다. 괄호의 value 를 가져온다. | |
| // i 는 string 에 저장된 문자를 뽑아쓰기 위한 변수 | |
| // length 는 string의 실제 길이 | |
| // tempInteger 는 integerList[idx] 를 빼서 저장한다. | |
| // result 는 tempInteger들의 값을 더해서 답을 출력해주기 위한 변수다. | |
| while(i != length){ // 마지막 문자가 아니라면 반복함 | |
| temp = string[i++]; // 하나씩 뽑는다 | |
| if(temp == '(' || temp == '['){ // 여는 괄호라면 | |
| idx++; | |
| if(temp == '(') | |
| integerList[idx] = 2 * integerList[idx-1]; | |
| if(temp == '[') | |
| integerList[idx] = 3 * integerList[idx-1]; | |
| characterList.push(temp); | |
| }else{ // 여는 괄호가 아니라면 | |
| if(characterList.empty()){ // 올바른 괄호가 아닐경우 | |
| result = 0; | |
| break; | |
| } | |
| compared = characterList.top(), characterList.pop(); // 스택에 저장된것을 뽑는다. | |
| tempInteger = integerList[idx--]; | |
| if(pre == ']' || pre == ')'){ | |
| tempInteger = 0; | |
| } | |
| if(compared == '(' && temp == ')'){ | |
| result += tempInteger; | |
| }else if(compared == '[' && temp == ']'){ | |
| result += tempInteger; | |
| }else{ // 올바른 괄호가 아닐경우 | |
| result = 0; | |
| break; | |
| } | |
| } | |
| pre = temp; | |
| } | |
| // 올바른 괄호가 아닐경우 | |
| if(characterList.size()) result = 0; | |
| printf("%d", result); | |
| return 0; | |
| } |
곱셈의 결합법칙을 이용해서 예외처리를 해줬다.
주석에 설명을 잘 달아놨다.
| BOJ 백준온라인져지 11866 조세퍼스 문제 0 풀이 (0) | 2017.11.29 |
|---|---|
| BOJ 백준온라인져지 10845 큐 풀이 (0) | 2017.11.29 |
| BOJ 백준온라인져지 1874 스택 수열 풀이 (0) | 2017.11.27 |
| BOJ 백준온라인져지 9020 골드바흐의 추측 풀이 (0) | 2017.11.25 |
| BOJ 백준온라인져지 4948 베르트랑 공준 풀이 (0) | 2017.11.24 |
| #include <cstdio> | |
| #include <stack> | |
| #include <vector> | |
| /** | |
| * https://www.acmicpc.net/problem/1874 | |
| * BOJ 백준온라인져지 1874 스택 수열 풀이 | |
| */ | |
| using namespace std; | |
| int main(){ | |
| stack <int> stack; | |
| vector <char> vector; // 문자열 하기 위한 벡터 | |
| int N,temp=0; // temp는 c배열에 있는 값을 조회할때 사용한다. | |
| int c[100000],idx=0; // c 배열에는 입력값을 차례대로 넣는다. | |
| scanf("%d",&N); | |
| while(N--) scanf("%d",&c[idx++]); // c배열에 넣는다. | |
| for(int i = 0; i<idx; i++){ | |
| stack.push(i+1); // stack에 차례대로 1 2 3 4 넣는다. | |
| vector.push_back('+'); // push는 +를 출력한다. | |
| while(stack.size() && stack.top() == c[temp]) // stack top 값에 c[temp]가 있으면 | |
| stack.pop(), temp++, vector.push_back('-'); // 꺼내고 temp++ -출력 | |
| } | |
| if(stack.size()) printf("NO"); // 스택에서 못 꺼낸값이 있으면 NO 출력 | |
| else{ // 아니면 vector에 들어있는 값을 차례대로 출력한다. | |
| for(int i = 0, size = vector.size(); i<size; i++) | |
| printf("%c\n",vector[i]); | |
| } | |
| return 0; | |
| } | |
| // class Node{ | |
| // public: | |
| // int number; | |
| // Node(int n); | |
| // Node next; | |
| // }; | |
| // Node::Node(int n){ | |
| // number = n; | |
| // } | |
| // class Stack{ | |
| // public: | |
| // Node head; | |
| // void push(int n); | |
| // int pop(); | |
| // int size(); | |
| // private: | |
| // int size = 0; | |
| // }; | |
| // void Stack::push(int n){ | |
| // Node node = new Node(n); | |
| // if(head != NULL){ | |
| // node.next = head; | |
| // } | |
| // head = node; | |
| // size++; | |
| // } | |
| // int Stack::pop(){ | |
| // if(head == NULL) return -1; | |
| // int number = head.number; | |
| // head = head.next; | |
| // size--; | |
| // return number; | |
| // } | |
| // int Stack::size(){ | |
| // return size; | |
| // } |
처음에 문제를 잘 못 이해해서,
8 4 3 6 8 7 5 2 1
이면
8 = n 이고
4번 +하고
4 - 3 + 1 만큼 -하고 이런식으로 되는 줄 알앗는데,
1~N까지 push하고 차례대로 pop해주는거였다.
| BOJ 백준온라인져지 10845 큐 풀이 (0) | 2017.11.29 |
|---|---|
| BOJ 백준온라인져지 2504 괄호의 값 풀이 (0) | 2017.11.28 |
| BOJ 백준온라인져지 9020 골드바흐의 추측 풀이 (0) | 2017.11.25 |
| BOJ 백준온라인져지 4948 베르트랑 공준 풀이 (0) | 2017.11.24 |
| BOJ 백준온라인져지 1181 단어 정렬 풀이 (0) | 2017.11.23 |