[알고리즘] 기본 추상자료형(5) - 예제(스택ADT)

[문제1] 스택을 이용하여 중위수식을 후위수식으로 변환하는 프로그램

- 피연산자는 영문자로 나타내고, 수식의 최대길이는 100

입력토큰	연산자	우선순위
! +(부호) -(부호)	단항연산자	6
* /	곱셈, 나눗셈	5
+ -	덧셈, 뺄셈	4
> <	관계연산자	3
&&	논리연산자(AND)	2
||	논리연산자(OR)	1

입력예시                출력예시

3 A*B+C+(D+E)*F A/B-C+D*E-F*G A&&B||C||!(E>F)

AB*C+DE+F*+ AB/C-DE*+FG*- AB&&C||EF>!||

#include<stdio.h> #include<stdlib.h> #include<string.h> int stackSize, top, sign; void push(char *stack, char value) { stack[++(top)] = value; } char pop(char *stack) { return stack[(top)--]; } int operand(char *inArray, int i){ if ((top != i) && (i == 0) && ((inArray[i] == '+') || (inArray[i] == '-'))){ sign = 1; return 6; } else if ((top != -1) && ((inArray[i] == '+') || (inArray[i] == '-')) && ((inArray[i - 1] == '|') || (inArray[i - 1] == '&') || (inArray[i - 1] == '<') || (inArray[i - 1] == '>') || (inArray[i - 1] == '-') || (inArray[i - 1] == '+') || (inArray[i - 1] == '*') || (inArray[i - 1] == '/') || (inArray[i - 1] == '!'))){ return 6; } else if (inArray[i] == '|'){ return 1; } else if (inArray[i] == '&'){ return 2; } else if (inArray[i] == '>' || inArray[i] == '<'){ return 3; } else if (inArray[i] == '+' || inArray[i] == '-'){ return 4; } else if (inArray[i] == '*' || inArray[i] == '/'){ return 5; } else if (inArray[i] == '!'){ return 6; } else{ return 0; } } void main(){ int calculateSize, number; char inArray[100], outArray[100], stack[100]; scanf("%d", &calculateSize); getchar(); for (int i = 0; i < calculateSize; i++){ number = 0, top = -1, sign = 0; for (int j = 0; j < 100; j++){ outArray[j] = '\0'; stack[j] = '\0'; } scanf("%s", inArray); getchar(); for(int j = 0; j < strlen(inArray); j++){ if (inArray[j] == '('){ push(stack, inArray[j]); } else if (inArray[j] == ')'){ while (stack[top] != '('){ outArray[number++] = pop(stack); } pop(stack); } else if (operand(inArray, j) == 6){ push(stack, inArray[j]); } else if (operand(inArray, j) == 0){ outArray[number++] = inArray[j]; } else{ if (sign == 1){ outArray[number++] = pop(stack); } else{ while ((top != -1) && (operand(inArray, j) <= operand(stack,top))){ outArray[number++] = pop(stack); } } if ((operand(inArray,j) == 1) || (operand(inArray, j) == 2)){ push(stack, inArray[j++]); } push(stack, inArray[j], top); } } while (top != -1){ outArray[number++] = pop(stack); } printf("%s\n", outArray); } }

[문제2] 후위수식을 받아 스택을 사용하여 계산한 후 결과 값을 출력하는 프로그램

- 피연산자는 0에서 9사이의 정수이고 수식의 최대길이는 100

#include<stdio.h> #include<stdlib.h> #include<string.h> int stackSize, top; void push(char *stack, char value) { stack[++(top)] = value; } char pop(char *stack) { return stack[(top)--]; } int operand(char inArray){ if (inArray == '+'){ return 1; } else if (inArray == '-'){ return 2; } else if (inArray == '*'){ return 3; } else if (inArray == '/'){ return 4; } else{ return 0; } } void main(){ int number, calculateNumber1, calculateNumber2, calculateSize; char inArray[100], stack[100]; scanf("%d", &calculateSize); for (int i = 0; i < calculateSize; i++){ top = -1; number = 0; scanf("%s", inArray); getchar(); while (number != strlen(inArray)){ if (operand(inArray[number]) == 0){ push(stack, inArray[number] - '0'); } else{ if (operand(inArray[number]) == 1){ calculateNumber1 = pop(stack); calculateNumber2 = pop(stack); push(stack, calculateNumber1 + calculateNumber2); } else if (operand(inArray[number]) == 2){ calculateNumber1 = pop(stack); calculateNumber2 = pop(stack); push(stack, calculateNumber2 - calculateNumber1); } else if (operand(inArray[number]) == 3){ calculateNumber1 = pop(stack); calculateNumber2 = pop(stack); push(stack, calculateNumber2 * calculateNumber1); } else if (operand(inArray[number]) == 4){ calculateNumber1 = pop(stack); calculateNumber2 = pop(stack); push(stack, calculateNumber2 / calculateNumber1); } } number++; } printf("%d\n", pop(stack, top)); } }