2484 산술 식 의 변환

산술 식 변환 Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description 샤 오 밍 은 데이터 구 조 를 공부 한 후에 예전 에 해결 하지 못 했 던 산술 표현 식 이 접미사 식 으로 바 뀌 었 던 문제 가 갑자기 생각 났 다. 오늘 그 가 해결 하고 자 한다.데이터 구조의 기초 가 있 기 때문에 샤 오 밍 은 곧 이 문 제 를 풀 었 다. 그러나 그 는 갑자기 산술 식 의 접두사 식 과 접두사 식 을 어떻게 구 해 야 할 지 생각 했다.샤 오 밍 은 매우 곤혹스럽다.똑똑 한 니 가 해결 해 줘.Input 은 산술 표현 식 을 입력 하여 \ '\ # \' 문 자 를 끝 표지 로 합 니 다.(데 이 터 는 빈 칸 이 없고 한 그룹 만 입력 할 수 있 습 니 다) 출력 출력 은 이 표현 식 에서 얻 은 접두사 식 접두사 식 접 두 사 를 출력 합 니 다.세 줄 로 나 누 어 출력 하고 순 서 는 접두사 식 접두사 식 입 니 다.Sample Input a*b+(c-d/e)*f# Sample Output +ab-c/def a*b+c-d/e*f ab*cde/-f*+ Hint
Source THINK: 스 택 의 저장 은 모든 것 을 한꺼번에 넣 는 것 이 아니 라 조작 하면 서 저장 하 는 것 입 니 다. 1. 접두사 표현 식 에서 접두사 표현 식 으로 전환 하 는 것 입 니 다. 두 개의 스 택 이 필요 합 니 다. 한 스 택 은 알파벳 을 저장 하고 다른 스 택 은 연산 자 를 저장 해 야 합 니 다.또한 접두사 표현 식 은 오른쪽 에서 왼쪽으로 시작 합 니 다.(이때 같은 상황 이 없 음 을 주의 하 십시오. 접미사 표현 식 과 다 릅 니 다. 접미사 표현 식 은 두 가지 상황 이 있 습 니 다. 현재 요 소 는 가감 이 고 스 택 꼭대기 의 요소 도 가감 입 니 다. 현재 요 소 는 곱셈 이 고 스 택 꼭대기 의 요소 도 곱셈 입 니 다)그리고 현재 요 소 는 스 택 에 들 어 갑 니 다. 2. 현재 요 소 는 왼쪽 괄호 일 때 오른쪽 괄호 를 찾 아야 합 니 다. 이 두 개의 괄호 를 제외 하고 그들 사이 의 요 소 를 모두 스 택 1 에 넣 어야 합 니 다. (접미사 표현 식 은 현재 왼쪽 괄호 이 고 오른쪽 괄호 를 찾 아야 합 니 다. 그리고 왼쪽 괄호 사이 의 요 소 는 출력 입 니 다. 다른 스 택 에 들 어 가 는 것 이 아 닙 니 다); 3. 다른 상황 은 창고 2 에 들 어가 면 됩 니 다. 그 다음 에 창고 2 안의 요 소 를 창고 1 에 정리 하고 마지막 에 창고 1 의 요 소 를 모두 출력 하면 됩 니 다. 접미사 표현 식 은 접미사 표현 식 으로 전환 합 니 다. 하나의 창고 만 있 으 면 연산 자 를 저장 하고 알파벳 을 만나면 출력 합 니 다. 연산 자 를 만나면 창고 에 들 어 갑 니 다. 여기 창고 에 들 어 가 는 조건 이 있 습 니 다. 1. 현재 요소 가 가감 되면 창고 꼭대기 에 있 는 요 소 는 조건 이 있 습 니 다.요 소 는 곱 하기, 스 택 꼭대기 요 소 는 먼저 출력 하고 현재 요 소 는 스 택 에 들 어 갑 니 다. 또는 현재 요 소 는 가감 입 니 다. 스 택 꼭대기 의 요소 도 가감 입 니 다. 또는 현재 요 소 는 곱 하기, 스 택 꼭대기 의 요소 도 곱 하기 입 니 다. 같은 작업 입 니 다. 2. 현재 요소 가 오른쪽 괄호 라면 스 택 에서 왼쪽 괄호 를 찾 고 왼쪽 괄호 를 제외 한 모든 연산 자 를 출력 해 야 합 니 다. 3. 다른 요 소 는 왼쪽 괄호 입 니 다.스 택 에 들 어간 경우 입 니 다. 마지막 으로 스 택 에 있 는 모든 요 소 를 출력 합 니 다. 2. 접두사 표현 식 과 접두사 표현 식 에 대한 연산: 접두사 표현 식: 스 택 에 작업 수 를 저장 해 야 합 니 다. 연산 자 를 만나면 스 택 꼭대기 요소 와 스 택 차 요 소 를 조작 해 야 합 니 다. 여기 서 작업 은 스 택 차 요소 가 스 택 꼭대기 요 소 를 가감 곱 한 다음 에 top 은 한 자리 물 러 나 야 합 니 다. 가장 좋 습 니 다.후 출력 스 택 꼭대기 의 값 을 사용 하면 됩 니 다. 접두사 표현 식: 오른쪽 에서 왼쪽으로 스 캔 작업 수 를 스 택 에 입력 하 는 것 입 니 다. 작업 할 때 스 택 꼭대기 요소 가 스 택 차 요 소 를 가감 곱 하 는 연산 입 니 다. 마지막 으로 스 택 꼭대기 요 소 를 출력 하면 됩 니 다.

#include
#include
#include
char z1[200],z2[200],s[200],a[200];
int main()
{
    scanf("%s",s);
    int len=strlen(s);
    int top=0,top1=0,top2=0;
    for(int i=len-2; i>=0; i--)
    {
        if(s[i]>='a'&&s[i]<='z')
        {
            z1[++top1]=s[i];
        }
        else if((s[i]=='+'||s[i]=='-')&&(z2[top2]=='*'||z2[top2]=='/'))//         ，     ，    s[i]=='+'||'-'，      

        {
            z1[++top1]=z2[top2];
            z2[top2]=s[i];
        }
        else if(s[i]=='(')
        {
            while(z2[top2]!=')')
            {
                z1[++top1]=z2[top2--];
            }
            top2--;
        }
        else
        {
            z2[++top2]=s[i];
        }
    }
    while(top2!=0)
    {
        z1[++top1]=z2[top2--];
    }
    while(top1!=0)
    {
        printf("%c",z1[top1--]);
    }
    printf("
");//        
    len=strlen(s);
    for(int i=0; i1;)
    {
        if(s[i]==')'||s[i]=='(')
        {
            i++;
        }
        else
        {
            printf("%c",s[i]);
            i++;
        }
    }
    printf("
");//        
    len=strlen(s);
    for(int i=0; i1; i++)
    {
        if(s[i]>='a'&&s[i]<='z')
        {
            printf("%c",s[i]);
        }
        else
        {
            if(((s[i]=='+'||s[i]=='-')&&(a[top]=='*'||a[top]=='/'))||
              ((s[i]=='+'||s[i]=='-')&&(a[top]=='+'||a[top]=='-'))||
              ((s[i]=='*'||s[i]=='/')&&(a[top]=='*'||a[top]=='/')))
            {
                printf("%c",a[top]);
                a[top]=s[i];
            }
            else if(s[i]==')')
            {
                while(a[top]!='(')
                {
                    printf("%c",a[top--]);
                }
                top--;
            }
            else
            {
                a[++top]=s[i];
            }
        }
    }
    while(top!=0)
    {
        printf("%c",a[top--]);
    }
    printf("
");//        
    return 0;
}