상용 데이터 구조 창고 의 응용 - 표현 식 값 구하 기

상용 데이터 구조 창고 의 응용 - 표현 식 값 구하 기
 

상용 데이터 구조 창고 의 응용 - 표현 식 값 구하 기

창고

표현 식 값 구하 기

접미사 표현 식 값 구하 기

접미사 표현 식 접미사 표현 식

코드 예시

 
창고.
스 택 은 자주 사용 하 는 데이터 구조 로 스 택 은 스 택 이 라 고도 부 르 며 제 한 된 선형 표 이다.표 의 한 끝 에 요 소 를 삽입 하고 삭제 할 수 있 도록 제한 합 니 다.스 택 에 있 는 요 소 는 후진 선 출 (FILO) 의 성질 에 부합 합 니 다.요 소 를 삽입 하고 삭제 할 수 있 는 한 끝 을 스 택 지붕 이 라 고 하고 다른 한 끝 은 스 택 바닥 이 라 고 합 니 다.창고 에는 두 가지 관건 적 인 조작 이 있 는데, 각각 창고 에서 나 오 는 것 과 창고 에서 나 오 는 것 이다.
창고 에는 두 가지 관건 적 인 조작 이 있 는데, 각각 창고 에서 나 오 는 것 과 창고 에서 나 오 는 것 이다.

스 택 (pop): 스 택 꼭대기 에 있 는 요소 E 를 삭제 하고 E 의 다음 요 소 를 새로운 스 택 꼭대기 라 고 부 르 며 요소 E

를 되 돌려 줍 니 다.

압축 창고 (push): 원소 E 를 창고 꼭대기 에 삽입 하여 새로 삽 입 된 원소 E 를 새로운 창고 꼭대기 라 고 부른다.

스 택 에서 흔히 볼 수 있 는 응용 은 주로 컴 파일 러 에서 문법 분석의 기호 일치, 표현 식 값 구하 기, 프로그램의 함수 호출 등 이 있다.예 를 들 어 운영 체제 의 프로 세 스 의 컨 텍스트 전환, CPU 프로 세 스 의 현장 정보, 예 를 들 어 레지스터 등 정 보 를 스 택 에 저장 하고 CPU 바퀴 가 이 프로 세 스 로 전 환 될 때 스 택 을 사용 하여 현장 을 복원 합 니 다.
표현 식 값 구하 기
표현 식 값 구 하 는 것 은 창고 의 중요 한 응용 이다.예 를 들 어 계산기 의 가감 승제 표현 식 의 계산 은 모두 스 택 을 사용 하여 값 을 구한다.표현 식 의 표현 방법 은 주로 접두사 표현법 과 접두사 표현법 이 있다.

접두사 표현법: 조작 기 호 는 두 조작 수의 중간 에 있 습 니 다. 예 를 들 어 3 + 4, 접두사 표현 식 은 사람들의 사고 에 부합 되 는 산술 표현 식 방법 입 니 다. 접두사 표현 식 은 보통 괄호 와 괄호 를 포함 합 니 다.접두사 표현 식 은 컴퓨터 에 의 해 이해 되 기 쉽 지 않 기 때문에 표현 식 으로 값 을 구하 기 가 쉽 지 않 습 니 다.
접두사 가 나타 내 는 예 1 + 3 * (4 + 5)

접미사 표현 식: 괄호 를 포함 하지 않 고 연산 기 호 는 두 연산 대상 의 뒤에 놓 으 며 모든 계산 은 연산 기호 가 나타 나 는 순서에 따라 엄격하게 왼쪽 에서 오른쪽으로 연산 합 니 다 (연산 기호의 우선 규칙 을 고려 하지 않 아 도 됩 니 다).
접미사 식 의 예 21 + 3 * 대응 접미사 식 은 (2 + 1) * 3

접미사 표현 식 값 구하 기
접미사 표현 식 을 사용 하여 값 을 구 할 때 괄호 와 연산 기호의 우선 규칙 을 고려 하지 않 고 왼쪽 에서 오른쪽으로 값 을 계산 하면 됩 니 다.
접미사 표현 식 의 값 구 하 는 과정 은:

조작 수 를 읽 고 스 택 에 눌 러 조작 자 를 읽 을 때 까지

조작 부호 로 읽 히 면 창고 꼭대기 의 앞의 두 요 소 를 창고 에서 꺼 내 이 조작 부 호 를 사용 하여 연산 하여 계산 결 과 를 얻는다

계산 결 과 를 창고 에 넣 기

표현 식 끝 날 때 까지 1, 2, 3 반복

마지막 스 택 에는 하나의 요소 만 있 고 마지막 계산 결과 로 변 합 니 다.창고 에서 내 보 내 면 됩 니 다.
예 를 들 어 접미사 표현 식 （2+1）*3 에 대응 하 는 접미사 표현 식 은 21+3* 입 니 다.

스 택 S 초기 화

읽 기 2 와 1 압 입 S, 이때 S 는 1,2

연산 자 + 를 읽 고 스 택 꼭대기 두 요 소 를 얻 을 수 있 습 니 다 1,2. 이때 스 택 이 비어 있 습 니 다

조작 부 호 를 사용 하여 두 조작 수 를 계산 하여 3（1 + 2 = 3） 를 얻 고 3 를 스 택 S 에 눌 러 넣 습 니 다. 이때 스 택 S 는 3

입 니 다.

읽 기 3, 스 택 S 에 눌 러 넣 습 니 다. 이때 스 택 은 3,3

입 니 다.

연산 자 * 를 읽 고 스 택 상단 두 요 소 를 얻 을 수 있 습 니 다 3，3 이때 스 택 S 가 비어 있 습 니 다

연산 자 * 를 사용 하여 두 요 소 를 연산 하여 얻 을 수 있 습 니 다 9. 9 를 스 택 S

에 눌 러 넣 습 니 다.

표현 식 끝 부분 읽 기

스 택 상단 요소 획득 9 즉 계산 결과 입 니 다.
컴퓨터 는 보통 접미사 표현 식 을 사용 하여 표현 식 값 을 구하 지만, 사람들 은 일반적으로 계산 하 는 표현 식 을 접미사 표현 식 으로 입력 합 니 다. 따라서 표현 식 값 을 구 할 때 접미사 표현 식 을 접미사 표현 식 으로 바 꾼 다음 접미사 표현 식 을 사용 하여 표현 식 값 을 구 해 야 합 니 다.접미사 표현 식 의 값 을 구 하 는 과정 은 매우 간단 합 니 다. 이미 위 에서 분석 하 였 습 니 다.현재 중요 한 단 계 는 접미사 표현 식 을 접미사 표현 식 으로 바 꾸 는 것 입 니 다.
접미사 식 접미사 식
접미사 표현 식 접미사 표현 식 은 표현 식 의 값 을 구 하 는 관건 적 인 단계 입 니 다. 그 과정 은 다음 과 같 습 니 다. 접미사 표현 식 IEXP 를 입력 하고 접미사 표현 식 SEXP 를 출력 하여 접미사 표현 식 IEXP 를 순서대로 읽 습 니 다. 스 택 S 를 초기 화하 여 연산 자 OP 를 저장 합 니 다.

동작 수 를 읽 으 면 SEXP 로 직접 출력 합 니 다.조작 부호 OP 이면 step 2 에 들 어가 고, 비어 있 으 면 IEXP 끝부분 을 읽 었 다 는 것 을 증명 하면 step 5

에 들 어 갑 니 다.

OP 를 판단 하고 만약 ( 이 라면 어떠한 출력 도 없 이 스 택 ( 에서 S 까지 step 1 에 들 어 갑 니 다.) 이면 스 택 S 의 요 소 를 SEXP 에 출력 하고 요소 ( 를 만 날 때 까지 ( SEXP 에 출력 하지 않 고 step 1 에 들 어 갑 니 다.OP 가 ( 와 ) 가 아니라면 step 3

을 실행 합 니 다.

스 택 S 의 스 택 꼭대기 요소 가 ( 인지 판단 하고 （ 이면 OP 를 S 에 직접 저장 합 니 다.( 가 아니라면 스 택 S 의 요 소 를 SEXP 에 출력 하고 스 택 상단 요소 의 우선 순위 가 OP 보다 작 거나 스 택 이 비 어 있 을 때 까지 step 4

에 들 어 갑 니 다.

OP 를 스 택 S 에 눌 러 step 1

에 들 어 갑 니 다.

스 택 의 모든 요 소 를 SEXP 에 출력 합 니 다

예 를 들 어 IEXP 는 （2+1）*3 이 고 빈 스 택 S 를 초기 화 합 니 다.

연산 자 ( 를 읽 고 스 택 S 에 직접 눌 러 넣 습 니 다. 이때 스 택 S 는 （、 입 니 다.

동작 수 2 를 읽 으 면 SEXP 로 직접 출력 합 니 다. 이때 S 는 （ 이 고 SEXP 는 2

입 니 다.

작업 기호 + 를 읽 었 습 니 다. 스 택 S 스 택 상단 요소 ( 이기 때문에 직접 + 을 스 택 S 에 눌 렀 습 니 다. 이때 SEXP 는 2 이 고 스 택 S 는 （、+

입 니 다.

동작 수 1 를 읽 고 직접 출력 합 니 다. 이때 SEXP 21, 스 택 S （、+ 입 니 다.

연산 자 ) 를 읽 으 면 스 택 S 의 요 소 를 만 날 때 까지 ( 출력 하지 않 음 ( 과 ), SEXP 21+, 스 택 S 가 비어 있 음

조작 기호 *' 를 읽 고 S 에 저장 합 니 다. 이때 SEXP 는 21+ 이 고 스 택 S 는 *

입 니 다.

동작 수 3 를 읽 고 SEXP 에 직접 출력 합 니 다. SEXP 는 21+3 이 고 스 택 S 는 *

입 니 다.

파일 끝 에 읽 으 면 스 택 S 는 스 택 이 비어 있 음 을 알 고 SEXP 는 21+3* 마지막 으로 접미사 표현 식 21+3* 을 얻 을 수 있 습 니 다. 접미사 의 관건 은 읽 은 연산 자가 괄호 인 case 입 니 다. 스 택 에 있 는 ( 은 연산 자 ) 를 만 날 때 까지 보류 합 니 다. 그렇지 않 으 면 스 택 에서 나 오지 않 습 니 다.

코드 예제

//int 
#include 
#include 
#define INCREMENT 20

struct Stack_{
    int* a;
    int capacity;
    int size;
    int top;
};

int pop_(struct Stack_* stack) {
    if(stack->size <= 0 || stack->top < 0)
        return NULL;
    stack->size--;
    return stack->a[stack->top--];
}

void push_(struct Stack_* stack, int c) {
    //  
    if(stack->size <= stack->capacity) {
        stack->capacity += INCREMENT;
        int* p = (int*)malloc(sizeof(int) * ( stack->capacity));
        int i;
        int* q;
        q = p;
        for(i = 0; i < stack->size; i++) {
            *(q++) = *(stack->a++);
        }
        stack->a = p;
    }

    //  
    stack->size++;
    stack->top++;
    stack->a[stack->top] = c;
}

struct Stack_* initStack_(int capacity) {
    struct Stack_* stack = (struct Stack_*)malloc(sizeof(struct Stack_));
    int* a = (int*)malloc(sizeof(int) * capacity);
    stack->size = 0;
    stack->top = -1;
    stack->a = a;
    return stack;
};

//            test  
int in(char* a, int n, char test) {
    int i = 0;
    for(i; i < n; i++) {
        if(a[i] == test)
            return 1;
    }
    return 0;
}

//     
int compare(char a, char b) {

    if(a == b)
        return 0;

    if(a == '+') {
        if(b == '*' || b == '(' || b == ')')
            return -1;
    }

    if(a == '*') {
        if(b == '+')
            return +1;
        if(b == '(' || b == ')')
            return -1;
    }
}

//            
char* infix2Suffix(char* infix, int n) {
    struct Stack* stack = initStack(n);
    char add = '+';
    char mult = '*';
    char left = '(';
    char right = ')';
    char op[4] = {'+', '*', '(', ')'};
    int i = 0;
    char *result = (char*)malloc(sizeof(char) * n);
    char top;
    int j = 0;

    for(i; i < n; i++) {
        char c = infix[i];
        //            ，    
        //           
        if(!in(op, 4, c))
            result[j++] = c;
        else {//        
            if(stack->size == 0)
                push(stack, c);
            else {
                //
                if(c != '(' && c != ')') {
                    while(1) {
                        top =  pop(stack);
                        if(top == NULL)
                            break;
                        if(top == '(' || compare(c, top) > 0) {
                            push(stack, top);
                            break;
                        } else if (compare(c, top) <= 0)
                            result[j++] = top;
                    }
                    push(stack, c);
                }

                if(c == '(')
                    push(stack, c);

                if(c == ')') {
                    while(1) {
                        top =  pop(stack);
                        if(top != NULL && top != '(')
                            result[j++] = top;
                        else
                            break;
                    }
                }


            }
        }
    }
    //         
    while(1) {
        top = pop(stack);
        if(top == NULL)
            break;
        result[j++] = top;
    }
    result[j++] = '#';
    return result;
}

//       
int evaluate(char* infix, int n) {
    char *suffix = infix2Suffix(infix, n);
    struct Stack_* stack = initStack_(n);
    char op[4] = {'+', '*', '(', ')'};
    int i = 0;
    char opnum1, opnum2;
    char c;

    while((c = suffix[i++]) != '#') {
        if(!in(op, 4, c))
            push_(stack, (int)c - (int)'0');
        else if(in(op, 4, c)){
            int opnum1 = pop_(stack);
            int opnum2 = pop_(stack);
            int tmp;
            if(c == '+')
                tmp = opnum1 + opnum2;
            if(c == '*')
                tmp = opnum1 * opnum2;
            push_(stack, tmp);
        }
    }

    return pop_(stack);
}

int main() {

    char infixExp[13] = {'6', '+', '5', '+', '7',
                        '*', '8', '*', '(', '1',
                        '+', '2', ')'};
    int result = evaluate(infixExp, 13);
    char *suffixExp = infix2Suffix(infixExp, 13);
    printf("
");
    while(*suffixExp!= '#')
        printf("%c", *suffixExp++);
    printf("
%d", result);
    return;
}

다음으로 전송:https://www.cnblogs.com/Spground/p/8536160.html