창고 응용: 접미사 표현 식 값 구하 기

접미사 표현 식 의 값 구 하 는 것 이 비교적 간단 합 니 다. 기본 적 인 과정 은 숫자 를 만나면 스 택 에 들 어가 고 연산 자 를 만나면 스 택 두 개의 숫자 를 계산 한 다음 에 결 과 를 스 택 에 넣 습 니 다. 과정 이 비교적 간단 합 니 다. 복습 하지 않 습 니 다. 다음은 접미사 표현 식 의 값 구 하 는 데 중심 을 두 고 기록 합 니 다.
접두사 표현 식 의 값 을 구 하려 면 먼저 접 두 사 를 접두사 로 바 꾸 고 접두사 로 결 과 를 계산 할 수 있 습 니 다. 그러나 너무 번 거 롭 습 니 다. 다른 방식 은 두 개의 스 택 을 이용 하여 직접 값 을 구 하 는 것 입 니 다. 사상 은 이전 필기 접두사 로 접 두 사 를 바 꾸 는 것 과 거의 같 지만 차이 가 있 습 니 다. 접두사 표현 식 의 값 구 하 는 것 은 기본적으로 다음 과 같 습 니 다.
두 개의 스 택 을 정의 합 니 다. stack 1 은 숫자 를 저장 하고 stack 2 는 연산 자 를 저장 합 니 다. 문자열 str 요 소 를 하나씩 스 캔 하고 숫자 형 을 만나면 스 택 stack 1 에 들 어 갑 니 다. 연산 자 형 을 만나면 스 택 stack 2 스 택 꼭대기 요소 연산 자 우선 순위 가 자신 보다 크 거나 같 는 지 확인 해 야 합 니 다. 만약 에 자신 보다 크 면 그 연산 자 는 스 택 에서 나 옵 니 다. 스 택 이 연산 자 a 라 고 가정 합 니 다.그러면 이때 stack 1 에서 두 개의 숫자 b, c 가 연산 에 참여 하고 연산 결 과 를 스 택 stack 1 에 들 어 갑 니 다. 이때 이 문 자 는 스 택 에 들 어 갈 수 없습니다. 만약 에 스 택 의 우선 순위 가 자신 보다 크 거나 같 으 면 그 스 택 의 연산 자 는 자신 보다 작은 자신 이 스 택 에 들 어 갈 때 까지 연산 을 해 야 합 니 다.'(' 직접 stack 2 에 들 어가, 만나다 ')' 를 만나면 이 괄호 사이 의 연산 자 를 하나씩 꺼 내 서 연산 해 야 한다. str [i] 가 '\ 0' 을 읽 으 면 스 캔 이 끝나 면 stack 2 에 연산 자가 하나 더 있어 야 한 다 는 것 을 주의해 야 한다. 그래서 한 걸음 더 연산 해 야 한다. 마지막 stack 1 에 한 개의 숫자 가 남 는 것 이 마지막 결과 이다.
실제로 위 는 모든 수 를 바탕 으로 한 자릿수 로 구성 되 어 있 습 니 다. 즉, 형 예 는 3 * (2 + 4) - 2 이지 형 예 는 30 * (20 + 44) - 2 가 아 닙 니 다. 아래 프로그램 도 한 자릿수 를 바탕 으로 합 니 다. 그러나 한 자릿수 프로그램 이 작 성 된 후에 읽 기 문 자 를 조금 만 조정 하면 임 의 표현 식 을 사용 할 수 있 습 니 다. 접두사 표현 식 의 값 을 깊이 이해 하기 위해 여러 비트 수 를 고려 하지 않 습 니 다.핵심 알고리즘 을 구현 할 수 있 는 한 자릿수 형 만 을 고려 하 다.

#include 
#include 
float Cal(char a,float b,float c)//    ，a    ,b、c     
{
    switch(a)
    {
    case '+':
        return (b+c);
        break;
    case '-':
        return (b-c);
        break;
    case '*':
        return (b*c);
        break;
    case '/':
        return (1.0*b/c);
        break;
    }
}


int main(void)
{
    float stack1[200];//     
    char stack2[100];//      
    int top1=-1,top2=-1;
    int i = 0;
    char str[200];
    char a;
    float b,c;


    FILE *fp=fopen("data.txt","r");//        ，         
    fscanf(fp,"%s",str);
    printf("%s
",str);
    while(str[i] != '\0')//         
    {
        if(str[i] == '+' || str[i] == '-')//  str[i]      ，               
        {
            if(top2==-1)//         ，      ，       2
            {
                stack2[++top2]=str[i];
            }
            else
            {
                while(stack2[top2] == '+' || stack2[top2] == '-' || stack2[top2] == '*' || stack2[top2] == '/')
                {
                    a=stack2[top2--];//      
                    c=stack1[top1--];//       
                    b=stack1[top1--];// 2       
                    stack1[++top1]=Cal(a,b,c);//       1
                    printf("
%f%c%f=%f
",b,a,c,stack1[top1]);//        
                }
                stack2[++top2]=str[i];//             2
            }
        }

        else if(str[i] == '*' || str[i] == '/')//  str[i]      ，                
        {
            if(top2==-1)//  
            {
                stack2[++top2]=str[i];
            }
            else
            {
                while(stack2[top2] == '*' || stack2[top2] == '/')
                {
                    a=stack2[top2--];//  
                    c=stack1[top1--];//  
                    b=stack1[top1--];//  
                    stack1[++top1]=Cal(a,b,c);//  
                    printf("
%f%c%f=%f
",b,a,c,stack1[top1]);//  
                }
                stack2[++top2]=str[i];//  
            }
        }

        else if(str[i] == '(')//  str[i]          2
        {
            stack2[++top2]=str[i];
        }

        else if(str[i] == ')')//  str[i]    ，                ，           
        {
            while(stack2[top2] != '(')
            {
                a=stack2[top2--];
                c=stack1[top1--];
                b=stack1[top1--];
                stack1[++top1]=Cal(a,b,c);
                printf("
%f%c%f=%f
",b,a,c,stack1[top1]);
            }
            stack2[top2--];//  
        }

        else//  str[i]          
        {
            stack1[++top1]=str[i]-'0';//  ，    
        }
        i++;
    }
    while(top2!=-1)//         ，       
    {
        a=stack2[top2--];
        c=stack1[top1--];
        b=stack1[top1--];
        stack1[++top1]=Cal(a,b,c);
        printf("
%f%c%f=%f
",b,a,c,stack1[top1]);
    }
    printf("
  ：%f
",stack1[top1]);
    return 0;
}

data.txt   ：
3*(2+4)-2