hdu 1237 접미사 표현 식 스 택 의 응용

요 며칠 동안 데이터 구조의 지식 을 예습 하고 있다.스 택 의 응용 접미사 표현 식 (역 폴란드 표현 식) 을 보 았 습 니 다.
접미사 표현 식: 연산 자 는 모두 숫자 뒤에 있 습 니 다. 먼저 접미사 표현 식 을 사용 해 야 합 니 다. 접미사 표현 식 에서 접미사 표현 식 으로 전환 하 는 방법 을 알 고 접미사 표현 식 에서 계산 하 는 방법 을 알 아야 합 니 다.우선 접미사 접미사 돌리 기:
표현 식 을 읽 고 숫자 를 접미사 표현 식 에 직접 출력 합 니 다. 기 호 는 스 택 꼭대기 요소 와 의 우선 순위 관 계 를 판단 합 니 다. 우선 순위 가 스 택 꼭대기 요소 의 우선 순위 보다 높 지 않 으 면 스 택 꼭대기 요 소 를 출력 하고 새로운 스 택 꼭대기 요 소 를 반복 합 니 다.마지막 까지 이 기 호 를 창고 에 넣 으 세 요.기호 가 오른쪽 괄호 라면 스 택 에서 만난 첫 번 째 왼쪽 괄호 사이 의 기 호 를 모두 출력 하고 괄호 는 출력 하지 않 습 니 다.
접미사 표현 식 으로 계산:
숫자 를 다른 숫자 를 저장 하 는 스 택 에 눌 러 넣 고 문 자 를 만나면 스 택 꼭대기 요 소 를 두 번 째 동작 으로 꺼 내 고 팝 업 을 하 며 하 나 를 첫 번 째 동작 으로 하고 팝 업 을 하 며 계산 결 과 를 다시 스 택 에 눌 러 넣 습 니 다.
처음 쓴 지 오래 되 었 는데 도 생각 이 뚜렷 하 다 고 말 할 수 없다.이 문 제 는 '\ #' 로 모든 숫자 와 조작 자 를 구분 했다. 구분 하지 않 으 면 여러 자리 의 숫자 인지 두 개의 숫자 인지 판단 할 수 없 기 때문이다.
접미사 표현 식 을 기록 하 는 배열 은 초기 화 하거나 경 계 는 strlen 을 사용 하지 않 는 것 을 기억 합 니 다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <cstring>
#include <cctype>
using namespace std;
#define M 1009
char a[M] = "+-*/";
int b[M] = {1,1,2,2};
char out[M];
char in[M];
stack<char> s; //     
int main()
{
    while(1)
    {
        //memset(out,'\0',sizeof(out));
        gets(in);
        if(strcmp(in,"0")==0)
            break;
        int k = 0;
        for(int i = 0;i < strlen(in);i++)
        {
            if(in[i]==' ') continue;
            if(isdigit(in[i]))
            {
                if(i < strlen(in)-1 && isdigit(in[i+1]))
                    out[k++] = in[i];
                else
                {
                    out[k++] = in[i];
                    out[k++] = '#';
                }
            }
            else
            {
                while(!s.empty())
                {
                    int p=-1,q=-1;
                    for(int j = 0;j < 4;j++)
                    {
                        if(a[j]==in[i])
                        {
                            p = j;
                        }
                        if(a[j]==s.top())
                        {
                            q = j;
                        }
                    }
                    if(p!=-1 && q!=-1)
                    {
                        if(b[p] <= b[q])
                        {
                            out[k++] = s.top();
                            out[k++] = '#';
                            s.pop();
                        }
                        else break;
                    }
                }
                s.push(in[i]);
            }
        }
        while(!s.empty())
        {
            out[k++] = s.top();
            out[k++] = '#';
            s.pop();
        }
        //printf("%s
",out);
        //int p = 0;
        double sum = 0;
        stack<double> ss;  //    
        int ok = 0;
        for(int i = 0;i < k;i++)  //             
        {
            if(isdigit(out[i]))
            {
                sum = 10*sum + out[i]-'0';
                ok = 1;
            }
            else
            {
                if(ok)
                {
                    ss.push(sum);
                    ok = 0;
                    sum = 0;
                }
                if(out[i]!='#')
                {
                    double one ,two;
                    one = ss.top();
                    ss.pop();
                    two = ss.top();
                    ss.pop();
                    double temp;
                    switch (out[i])
                    {
                    case '+':
                        temp = one+two;
                        ss.push(temp);
                        break;
                    case '-':
                        temp = two-one;
                        ss.push(temp);
                        break;
                    case '*':
                        temp = one*two;
                        ss.push(temp);
                        break;
                    case '/':
                        temp = (double)two/one;
                        ss.push(temp);
                        break;
                    }
                }
            }
        }
        if(!ss.empty())
        printf("%.2f
",ss.top());
        while(!ss.empty()) ss.pop();
        while(!s.empty())s.pop();
    }
    return 0;
}