ACM 문제 풀이 길 (11) 더미, 스 택, 대기 열 표현 식 변환

이것 은 이라는 과목 의 방과 후 연습 문제 로 매우 전형 적 인 문제 로 정리 하고 기록 하 는 것 이다.
제목: 표현 식 변환 
산술 표현 식 은 접두사 표현법, 접두사 표현법 과 접두사 표현법 등 형식 이 있다.일상적으로 사용 하 는 산술 표현 식 은 두 개의 연산 수 중간 에 있 는 접두사 표현법, 즉 이원 연산 자 를 사용한다.디자인 프로그램 에서 접미사 표현 식 을 접미사 표현 식 으로 변환 하 십시오.
입력 형식:
한 줄 에 빈 칸 이 없 는 접두사 표현 식 을 입력 하 십시오.
출력 형식:
한 줄 에서 변 환 된 접미사 표현 식 을 출력 하려 면 서로 다른 대상 (연산 수, 연산 기호) 사이 에 빈 칸 으로 구분 해 야 하지만 끝 에 빈 칸 이 있어 서 는 안 됩 니 다.
입력 예시:
2+3*(7-4)+8/4

출력 예시:
2 3 7 4 - * + 8 4 / +

예 를 들 어 a + b * c + (d * e + f) * g
string 형식 읽 기
알파벳 을 만나면 바로 대기 열 에 들 어 갑 니 다.
곱셈 나 누 기 우선 순위 가 가감 법보 다 높다
우선 순위 높 은 입 소
우선 순위 가 같 거나 낮은 것 은 먼저 높 은 것 을 대열 에 넣 은 다음 에 현재 의 것 을 창고 에 넣 습 니 다.
하면, 만약, 만약... 
')' 를 만나면 스 택 에서 '(') 를 찾 을 때 까지 머리 를 찾 고 스 택 에 있 는 '(') 을 삭제 합 니 다.
#include
#include
#include
#include
using namespace std;

int main(){

    stack s1;
    queue q1;
    while (!s1.empty())
        s1.pop();//     
    while (!q1.empty())
        q1.pop();//     

    string s;
    getline(cin, s);//  
    int len = s.size(), num = 0, i, j;

    for (i = 0; i < len; i++){
        string ts = "";
        char c = s[i], prc = s[i - 1];//c        prc        
        if ((c == '+' || c == '-') && (!i || prc == '(') || (c >= '0' && c <= '9'))
        {//                              
            if (c != '+') ts += c;
            while (s[i + 1] == '.' || s[i + 1] >= '0' && s[i + 1] <= '9')//         
                ts += s[++i];//       ts string 
            q1.push(ts);//    
        }
        else if (c == '+' || c == '-')
        {
            int flag = 1;//flag          (-4)       
            while (flag)
            {
                if (s1.empty() || s1.top() == "(")//   (-4)       
                    s1.push(ts + c), flag = 0;//             ,  
                else
                {
                    q1.push(s1.top());//       ,       ,     
                    s1.pop();
                }
            }
        }
        else if (c == '*' || c == '/')
        {
            int flag = 1;
            while (flag)
            {
                if (s1.empty() || s1.top() == "(" || s1.top() == "+" || s1.top() == "-")
                    s1.push(ts + c), flag = 0;//            ,   
                else
                {
                    q1.push(s1.top());//             
                    s1.pop();
                }
            }
        }
        else if (c == '(')//         
            s1.push(ts + c);
        else if (c == ')')//               
        {
            int flag = 1;
            while (flag)
            {
                string tp = s1.top();
                if (tp == "(") s1.pop(), flag = 0;//         
                else
                {
                    q1.push(s1.top());//         
                    s1.pop();
                }
            }
        }
    }
    while (!s1.empty())
    {
        q1.push(s1.top());//           
        s1.pop();
    }
    if (!q1.empty())
    { //c_str()    string   C      
        printf("%s", q1.front().c_str()); q1.pop();
    }//  string     %s    
    while (!q1.empty())
    {
        printf(" %s", q1.front().c_str()); q1.pop();
    }
    puts("");
    return 0;
}

좋은 웹페이지 즐겨찾기