C 언어 구현 계산기 - 접미사 표현 식

평소에 우리 가 쓴 산술 표현 식 은?
12 * ( 3 + 4 ) - 6 + 8 / 2
이러한 습관 적 인 표기 법 은 접미사 표현 식 이지 만 컴퓨터 의 일반적인 운행 방식 은 접미사 표현 식 으로 왼쪽 에서 오른쪽으로 순서대로 실 행 됩 니 다.
12 3 4 + * 6 - 8 2 / +
이게 접미사 표현 식 이에 요.
이게 어떻게 바 뀌 었 냐 면 요.
두 가지 가 있 습 니 다.
오늘 은 주로 스 택 전환 을 말 합 니 다.
접미사 표현 식 을 접미사 표현 식 으로 변환 합 니 다.
1. 스 택 만 들 기 2. 왼쪽 에서 오른쪽으로 접미사 표현 식 가 져 오기
a. 숫자 직접 출력 b. 연산 자
'(' 스 택 에 직접 들 어가 서 만 났 습 니 다 ')' 스 택 에 있 는 '(' 그 다음 에 스 택 에 들 어 가 는 모든 출력, 동시에 '(' 스 택 에서 나 오지 만 출력 하지 않 습 니 다. 다른 기 호 는 기호 스 택 에 있 는 요 소 를 순서대로 스 택 에서 나 와 출력 합 니 다. 현재 기호 보다 우선 순위 가 낮은 기호 나 '(') 를 만 날 때 까지 현재 기 호 를 스 택 에 넣 습 니 다.
3. 가 져 온 후 스 택 에 남 은 기 호 를 순서대로 출력 합 니 다.
예 를 들 어 12 * (3 + 4) - 6 + 8 / 2 순서대로 가 져 오기: 12, 숫자, 직접 출력
접미사 표현 식: 12 기호 스 택:
'*', 연산 자 입 니 다.
접미사 표현 식: 12 심 볼 릭 스 택: *
'(', 왼쪽 괄호, 바로 창고 에 들 어 갑 니 다.
접미사 표현 식: 12 기호 스 택: * (
3, 숫자, 출력
접미사 표현 식: 12 3 기호 스 택: * (
'+', 연산 자, 입고
접미사 표현 식: 12 3 기호 스 택: * (+)
4, 숫자, 출력
접미사 표현 식: 12, 3, 4 기호 스 택: * (+)
')', 오른쪽 괄호, 스 택 의 요 소 는 순서대로 스 택 에서 나 오고 출력 은 왼쪽 괄호 를 만 나 는 것 을 알 고 왼쪽 괄호 도 스 택 에서 나 와 출력 하지 않 습 니 다.
접미사 표현 식: 12, 3, 4 + 기호 스 택: *
'-', 연산 자, 감호 의 우선 순위 가 곱 하기 보다 낮 기 때문에 곱 하기 번 호 를 창고 에서 내 보 내 고 출력 합 니 다. 이때 역 안에 기호 가 없고 감호 가 창고 에 들 어 갑 니 다.
접미사 표현 식: 12, 3, 4 + * 기호 스 택: -
6, 숫자, 출력
접미사 표현 식: 12, 3, 4 + * 6 기호 스 택: -
'+', 연산 자, 우선 순 위 는 감호 와 같 습 니 다.
접미사 표현 식: 12, 3, 4 + * 6 - 기호 스 택: +
8, 숫자, 출력
접미사 표현 식: 12, 3, 4 + * 6 - 8 기호 스 택: +
'/', 연산 자, 감호 의 우선 순위 보다 높 으 면 바로 스 택 에 들 어 갑 니 다.
접미사 표현 식: 12, 3, 4 + * 6 - 8 기호 스 택: + /
2, 숫자, 출력
접미사 표현 식: 12, 3, 4 + * 6 - 82 기호 스 택: + / 접미사 표현 식 을 가 져 온 후 스 택 에 남 은 요 소 를 순서대로 스 택 출력 접미사 표현 식: 12, 3, 4 + * 6 - 8, 2 / + 기호 스 택:
이상 은 접미사 표현 식 접미사 표현 식 이 바 뀌 었 을 때 도 접미사 표현 식 이 어떻게 계산 되 는 지, 스 택 을 이용 하 는 지 알 아야 합 니 다.

순서대로 옮 겨 다 니 기

숫자 여 부 를 검사 하고 숫자 라면 스 택 을 누 르 는 것 입 니 다. 조작 부호 가 스 택 에서 현재 조작 수의 오른쪽 조작 수 와 왼쪽 조작 수 를 순서대로 꺼 내 현재 조작 부호 와 연산 한 결과 스 택 을 누 르 는 것 입 니 다.

옮 겨 다 니 기 가 끝나 면 운행 결 과 는 스 택 꼭대기 요소 입 니 다. 예 를 들 어 12, 3, 4 + * 6 - 8, 2 / +

숫자 입력
창고

'+', 연산 자 를 만 나 스 택 에서 현재 조작 수의 오른쪽 조작 수 와 왼쪽 조작 수 를 순서대로 추출 하여 현재 조작 자 와 연산 한 결과 스 택 을 누 르 고 3 + 4 = 7
창고

'*', 연산 자, 12 * 7 = 84
창고

6, 입고
창고

'-', 연산 자, 84 - 6 = 78
창고

82, 입고
창고

'/', 연산 자, 8 / 2 = 4
창고

'+', 연산 자 78 + 4 = 82
창고

마지막 결 과 는: 82
다음은 접미사 식 계산 에 관 한 함수 입 니 다. 참고 하 실 수 있 습 니 다.
구조 체 정의:

#define max 100
typedef char DataType;
typedef struct Stack // 
{
    int top;
    DataType stack[max];
}Stack;

enum {Data,Add,Sub,Mul,Div}operate; //  

typedef struct Cell  
{
    enum operate op;
    int data;
}cell;

주요 함수:

void StackInit(Stack* p) //     
{
    assert(p);
    p->top = 0;
}
void StackPush(Stack* p, DataType data) //  
{
    assert(p);
    if (p->top <= max)
    {
        p->stack[p->top] = data;
        p->top++;
    }
    else
    {
        printf("stack fill
");
    }
}
int StackPop(Stack* p)//  
{
    //int ch;
    assert(p);
    if (p->top != 0)
    {
        p->top--;
        //ch = p->stack[p->top];
        return p->stack[p->top];
    }

}
int StackTop(Stack* p)//     
{
    int n;
    assert(p);
    if(p->top)
    {
        n = p->top;
        return p->stack[n-1];
    }

    return 0;
}
int CalRPN(cell* RPN, int sz)//      （     ）
{
    int i = 0;
    Stack s;
    assert(RPN);
    StackInit(&s);
    for (; i < sz; i++)  //    
    {
        int left = 0;//    
        int right = 0;//    
        switch (RPN[i].op) //swatch              ，        
        {
        case Data:
            StackPush(&s, RPN[i].data);      //  
            break;
        case Add:                             //  
            right = StackPop(&s);             //        
            left = StackPop(&s);
            StackPush(&s, right + left);      //    
            break;
        case Sub:                               //  
            right = StackPop(&s);
            left = StackPop(&s);
            StackPush(&s, left - right);
            break;
        case Mul:                            //  
            right = StackPop(&s);
            left = StackPop(&s);
            StackPush(&s, left * right);
            break;
        case Div:                            //  
            right = StackPop(&s);
            left = StackPop(&s);
            if (0 == right)
                printf("    
");
            else
                StackPush(&s, left / right);
            break;
        }
    }
    return StackTop(&s);
}

테스트:

void RPNTest()
{   //     cell             ，        ，          ，       ；
    cell RPN[] = { {Data,12},{Data,3},{Data,4},{Add,0},{Mul,0},{Data,6},
                   {Sub,0},{Data,8},{Data,2},{Div,0},{Add,0} };
    int sz = sizeof(RPN) / sizeof(RPN[0]);
    int ret = CalRPN(RPN, sz);
    printf("%d
", ret);
}