후위식 계산프로그램은 피연산자를 스택에 push하고 연산자를 만났을 때 pop하여 연산 후 다시 push하는 과정이었지만

중위수식을 후위식으로 변환하는 프로그램은 반대로 연산자를 push하고 피연산자는 그대로 출력합니다.


중위 수식을 후위 수식으로 변환할 떄 중요한 것은 연산자의 우선순위입니다.

괄호와 숫자로 구성된 중위 수식을 후위 수식으로 변환 할 때 연산자의 순위는 다음과 같습니다.


괄호 < +, - 연산자 < *, / 연산자


가장 중요한 것은 현재 처리중인 연산자와 스택에 있는 연산자의 우선순위를 이용한 처리 입니다.


1. 현재 처리 중인 연산자의 우선순위가 스택에 있는 연산자의 우선순위보다 낮을 때 

예를들어) 처리중인 연산자: + or - ,  스택에있는 연산자: * or / 일 때

=> 스택에 있는 연산자를 pop 해서 출력 후 처리 중인 연산자를 push 합니다.


2. 현재 처리 중인 연산자의 우선순위가 스택에 있는 연산자의 우선순위보다 클 때

예를들어) 처리중인 연산자: * or / , 스택에 있는 연산자: +, - 일 때

=> 현재 처리 중인 연산자를 그냥 push합니다.


3. 현재 처리중인 연산자의 우선순위와 스택에 있는 연산자의 우선순위가 같을 때

예를들어) 처리중인 연산자: +, 스택에 있는 연산자: - 일 때

=> 1번 경우와 똑같이 처리한다.

이유는 간단한 예시를 들면 쉽게 알 수 있습니다.

ex) 5-4+3일 때, 5/4*3 일 때 

=> 우선순위를 어떻게 하느냐에 따라 답이 달라집니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 100
typedef struct
{
    char data[max];
    int top;
}stackType;
 
int check(char* exp);
void init(stackType* s);
void push(stackType* s, char x);
int pop(stackType* s);
int is_full(stackType* s);
int is_empty(stackType* s);
char peek(stackType* s);
void infix_to_postfix(const char* s);
int prec(char op);
int main()
{
    
    infix_to_postfix("(2+3)*4+9");
    return 0;
}
void init(stackType* s)
{
    s->top = -1;
}
int is_full(stackType* s)
{
    return s->top == max - 1;
}
int is_empty(stackType* s)
{
    return s->top == -1;
}
void push(stackType* s, char x)
{
    if (is_full(s))
    {
        fprintf(stderr, "원소가 다 찼습니다.\n");
        return;
    }
    s->data[++(s->top)] = x;
}
char peek(stackType* s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "원소가 없습니다.\n");
        exit(1);
    }
    return s->data[(s->top)];
}
int pop(stackType* s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "원소가 없습니다\n");
        exit(1);
    }
    return s->data[(s->top)--];
}
void infix_to_postfix(const char* s)
{
    char ch,top_op;
    int n = strlen(s);
    stackType st;
    init(&st);
    for (int i = 0; i < n; i++)
    {
        ch = s[i];
        switch (ch)
        {
        case '+': case '-':case '*':case '/':
            while (!is_empty(&st) && (prec(ch) <= prec(peek(&st))))
            {
                printf("%c", pop(&st));
            }
            push(&st, ch);
            break;
        case '(':
            push(&st, ch);
            break;
        case ')':
            top_op = pop(&st);
            while (top_op != '(')
            {
                printf("%c", top_op);
                top_op = pop(&st);
            }
            break;
            //숫자일 떈 그대로 출력
        default:
            printf("%c", ch);
            break;
        }
    }
        //아직 스택에 남아있다면 다 뽑아냄
        while (!is_empty(&st))
            printf("%c", pop(&st));
    
}
int prec(char op)
{
    switch (op)
    {
    case '(':case ')': return 0;
    case '+':case '-': return 1;
    case '*':case '/':return 2;
    }
    return -1;
}
 
cs


결과





저작자표시

'자료구조 > 스택' 카테고리의 다른 글

스택을 이용한 후위 표기식 계산 프로그램  (0) 2020.04.09
스택을 이용한 괄호검사 프로그램  (0) 2020.04.09
top변수와 스택배열을 구조체로묶은 스택 구현  (0) 2020.04.09
구초체배열을 이용한 스택 구현  (2) 2020.04.09
전역 변수를 이용한 간단한 스택 구현  (0) 2020.04.09


주의할 것은 스택에 있는 피연산자를 뽑아낼 때 op1, op2의 순서입니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 100
typedef struct
{
    char data[max];
    int top;
}stackType;
 
int check(char* exp);
void init(stackType* s);
void push(stackType* s, int x);
int pop(stackType* s);
int is_full(stackType* s);
int is_empty(stackType* s);
int eval(const char* s);
int main()
{
    int result;
    puts("82/3-32*+ 계산하기\n");
    result = eval("82/3-32*+");
    printf("결과값은%d\n", result);
}
void init(stackType* s)
{
    s->top = -1;
}
int is_full(stackType* s)
{
    return s->top == max - 1;
}
int is_empty(stackType* s)
{
    return s->top == -1;
}
void push(stackType* s, int x)
{
    if (is_full(s))
    {
        fprintf(stderr, "원소가 다 찼습니다.\n");
        return;
    }
    s->data[++(s->top)] = x;
}
int pop(stackType* s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "원소가 없습니다\n");
        exit(1);
    }
    return s->data[(s->top)--];
}
int eval(const char* s)
{
    int op1, op2, value;
    int len = strlen(s);
    char ch;
    stackType st;
    init(&st);
    for (int i = 0; i < len; i++)
    {
        ch = s[i];
        if (ch != '+' && ch != '*' && ch != '/' && ch != '-')
        {
            value = ch - '0';
            push(&st, value);
        }
        else
        {
            //op1, op2 순서 조심, op2가 최근에 넣은 피연산자임
            op2 = pop(&st);
            op1 = pop(&st);
            switch (ch)
            {
            case '+': push(&st,op1 + op2); break;
            case '-':push(&st,op1 - op2); break;
            case '*': push(&st,op1 * op2); break;
            case '/': push(&st,op1 / op2); break;
            }
        }
    }
    return pop(&st);
 
}
cs


결과




저작자표시

'자료구조 > 스택' 카테고리의 다른 글

중위 수식을 후위 수식으로 변환하는 프로그램  (0) 2020.04.09
스택을 이용한 괄호검사 프로그램  (0) 2020.04.09
top변수와 스택배열을 구조체로묶은 스택 구현  (0) 2020.04.09
구초체배열을 이용한 스택 구현  (2) 2020.04.09
전역 변수를 이용한 간단한 스택 구현  (0) 2020.04.09


괄호가 들어간 문장을 입력하고 괄호가 올바르게 표현되었을 때와 틀렸을 때를 표현하는 프로그램 만들기

주의: 띄어쓰기 들어간 문자열의 입력? fgets함수사용하기 (gets함수는 비표준함수라 사용X)



코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 100
typedef struct
{
    char data[max];
    int top;
}stackType;
 
int check(char* exp);
void init(stackType* s);
void push(stackType* s, int x);
int pop(stackType* s);
int is_full(stackType* s);
int is_empty(stackType* s);
int main()
{
    stackType s;
    char exp[20];
    fgets(exp, sizeof(exp), stdin);
    if (check(exp) == 1)
        puts("성공!");
    else
        puts("실패!");
    return 0;
}
void init(stackType* s)
{
    s->top = -1;
}
int is_full(stackType* s)
{
    return s->top == max - 1;
}
int is_empty(stackType* s)
{
    return s->top == -1;
}
void push(stackType* s, int x)
{
    if (is_full(s))
    {
        fprintf(stderr, "원소가 다 찼습니다.\n");
        return;
    }
    s->data[++(s->top)] = x;
}
int pop(stackType* s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "원소가 없습니다\n");
        exit(1);
    }
    return s->data[(s->top)--];
}
int check(char* exp)
{
    stackType s;
    char ch, open_ch;
    int n = strlen(exp);
    init(&s);
    for (int i = 0; i < n; i++)
    {
        ch = exp[i];
        switch (ch)
        {
        case '(':case '[':case'{':
            push(&s, ch);
            break;
        case ')':case']':case'}':
            if (is_empty(&s))return 0;
            else
            {
                open_ch = pop(&s);
                if ((open_ch == '(' && ch != ')') || (open_ch == '{' && ch != '}') ||
                    (open_ch == '[' && ch != ']'))
                    return 0;
                
            }
            break;
        }
    }
    //괄호검사 다했는데 스택에 원소가 남아있다면? => 잘못된 수식
    if (!is_empty(&s))return 0;
    return 1;
}
cs


결과





저작자표시

'자료구조 > 스택' 카테고리의 다른 글

중위 수식을 후위 수식으로 변환하는 프로그램  (0) 2020.04.09
스택을 이용한 후위 표기식 계산 프로그램  (0) 2020.04.09
top변수와 스택배열을 구조체로묶은 스택 구현  (0) 2020.04.09
구초체배열을 이용한 스택 구현  (2) 2020.04.09
전역 변수를 이용한 간단한 스택 구현  (0) 2020.04.09


스택에 1,2,3 삽입 후 모든 원소를 삭제함과 동시에 출력하고 스택이 비었으면 1, 아니면 0 출력하기


top변수와 스택배열을 하나의 구조체로 묶고, 구조체 변수를 이용하여 포인터로 값을 수정하는 방식의 장점

=> 구조체 변수를 여러 개 선언 함으로서 스택을 여러개 구현하기 쉬움



코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
#include<stdlib.h>
 
#define max 5
typedef struct
{
    int stack[max];
    int top;
}stackType;
void init(stackType* s);
void push(stackType* s, int x);
int pop(stackType* s);
int is_full(stackType* s);
int is_empty(stackType* s);
 
int main()
{
    stackType st;
    //스택 초기화 하기
    init(&st);
    push(&st, 1); push(&st, 2), push(&st, 3);
    printf("%d\n", pop(&st));
    printf("%d\n", pop(&st));
    printf("%d\n", pop(&st));
    printf("스택이 비었는지 ? %d\n", is_empty(&st));
}
void init(stackType* s)
{
    s->top = -1;
}
int is_full(stackType* s)
{
    return s->top == max - 1;
}
int is_empty(stackType* s)
{
    return s->top == -1;
}
void push(stackType* s, int x)
{
    if (is_full(s))
    {
        fprintf(stderr, "원소가 다 찼습니다.\n");
        return;
    }
    s->stack[++(s->top)] = x;
}
int pop(stackType* s)
{
    if (is_empty(s))
    {
        fprintf(stderr, "원소가 없습니다\n");
        exit(1);
    }
    return s->stack[(s->top)--];
}
cs


결과




저작자표시

'자료구조 > 스택' 카테고리의 다른 글

중위 수식을 후위 수식으로 변환하는 프로그램  (0) 2020.04.09
스택을 이용한 후위 표기식 계산 프로그램  (0) 2020.04.09
스택을 이용한 괄호검사 프로그램  (0) 2020.04.09
구초체배열을 이용한 스택 구현  (2) 2020.04.09
전역 변수를 이용한 간단한 스택 구현  (0) 2020.04.09


학생의 이름, 주소, 학번을 하나의 구조체로 묶어서 구조체 스택배열로 3명의 정보 저장 후 모든 학생의 정보 출력 후 

1명을 삭제하고 삭제한 학생의 정보 출력시키기


핵심: 각 구조체 배열스택 내부의 문자열을 어떻게 입력받을까?


strcpy이용하기


1) 입력받지않고 직접 설정 하기

strcpy(stack[i].name,"홍길동");

2) 입력받아서 저장하기

방법1: scanf("%s",stack[i].name);

방법2: char name[10]; scanf("%s",name); strcpy(stack[i].name,name);


주의

2) 방법 사용시

stack[i].name =name;   => 잘못된 코드

배열의 주소값을 임의로  다른 주소로값으로 지정할 수 없음! => strcpy함수 이용하기


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#pragma warning(disable:4996)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max 5
typedef struct
{
    char name[10];
    char add[10];
    int id;
}info;
int top = -1;
info stack[max];
void push(info item);
info pop();
int is_full();
void show();
int main()
{
    info std_info;
    for (int i = 0; i < 3; i++)
    {
        scanf("%s%s%d", std_info.name, std_info.add, &std_info.id);
        push(std_info);
    }
    show();
    std_info = pop();
    printf("삭제한 학생의 이름은%s\n", std_info.name);
    printf("삭제한 학생의 주소는%s\n", std_info.add);
    printf("삭제한 학생의 학번은%d\n", std_info.id);
}
void push(info item)
{
    if (is_full())
    {
        fprintf(stderr, "원소가 다찼어요\n");
        return;
    }
    stack[++top] = item;
}
int is_full()
{
    if (top == max - 1) // 찼으면 -1 , 아니면 0반환
        return 1;
    else return 0;
}
int is_empty()
{
    return top == -1; //비었으면 1 , 아니면 0 반환
}
info pop()
{
    if (is_empty())
    {
        fprintf(stderr, "원소가 없어요\n");
        exit(1);
    }
    return stack[top--];
}
void show()
{
    if (is_empty())
    {
        fprintf(stderr, "원소가 없어요\n");
        return;
    }
    for (int i = 0; i <= top; i++)
    {
        printf("이름:%s 주소:%s 학번:%d\n", stack[i].name, stack[i].add, stack[i].id);
    }
}
cs


결과





저작자표시

'자료구조 > 스택' 카테고리의 다른 글

중위 수식을 후위 수식으로 변환하는 프로그램  (0) 2020.04.09
스택을 이용한 후위 표기식 계산 프로그램  (0) 2020.04.09
스택을 이용한 괄호검사 프로그램  (0) 2020.04.09
top변수와 스택배열을 구조체로묶은 스택 구현  (0) 2020.04.09
전역 변수를 이용한 간단한 스택 구현  (0) 2020.04.09


1,2, 3 삽입 후 1, 2 빼고 현재 탑원소(3)출력후 남아있는 원소 제거 후에  없는 원소를 뺐을때 오류 문구 나오게 하기


전역변수로 top변수 이용 시 문제점 

1. 하나 이상의 스택을 구현하려면 여러개의 top변수를 사용해야하나?(top1, top2...)

-> 너무 비효율적임

해결: top변수와 스택배열을 하나의 구조체로 결합시켜서 포인터로 이용하기 


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//1 2 3 삽입 후 1 2 빼고 현재 탑원소(3)출력후 다 빼고 없는 원소를 뺐을때 오류 문구 나오게
#include<stdio.h>
#include<stdlib.h>
#define max 5
int top = -1;
int stack[max];
void push(int x);
void pop();
void peek();
int is_full();
int main()
{
    push(1); push(2); push(3); pop(); pop(); peek(); pop(); pop();
}
void push(int x)
{
    if (is_full())
    {
        fprintf(stderr, "원소가 다찼어요\n");
        return;
    }
    stack[++top] = x;
}
int is_full()
{
    if (top == max - 1) // 찼으면 -1 , 아니면 0반환
        return 1;
    else return 0;
}
int is_empty()
{
    return top == -1; //비었으면 1 , 아니면 0 반환
}
void pop()
{
    if (is_empty())
    {
        fprintf(stderr, "원소가 없어요\n");
        return;
    }
    top--;
}
 
void peek()
{
    if (is_empty())
    {
        fprintf(stderr, "원소가 없습니다\n");
        return;
    }
    printf("스택의 top 원소는 %d입니다\n", stack[top]);
}
cs


저작자표시

'자료구조 > 스택' 카테고리의 다른 글

중위 수식을 후위 수식으로 변환하는 프로그램  (0) 2020.04.09
스택을 이용한 후위 표기식 계산 프로그램  (0) 2020.04.09
스택을 이용한 괄호검사 프로그램  (0) 2020.04.09
top변수와 스택배열을 구조체로묶은 스택 구현  (0) 2020.04.09
구초체배열을 이용한 스택 구현  (2) 2020.04.09

+ Recent posts

티스토리툴바