UVa 327 - Evaluating Simple C Expressions

327-Evaluating Simple C Expressions
3763
30.56%
1145
70.66%
제목 링크:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=263
샘플 입력:

a + b
b - z
a+b--+c++
c+f--+--a
   f-- + c-- + d-++e

샘플 출력:

Expression: a + b
    value = 3
    a = 1
    b = 2
Expression: b - z

제목 의 대의:
표현 식 을 주 십시오.표현 식 의 변 수 는 26 개의 소문 자로 구성 되 어 있 습 니 다.이 26 개의 자 모 는 순서대로 초기 값 을 1,2,3,...26 으로 나 누고 표현 식 의 변 수 는 중복 되 지 않 습 니 다.연산 자 는+,-,+,-(자체 증가 와 자체 감소 에 접두사 와 접두사 가 있 습 니 다).
그리고 이 표현 식 의 값 을 출력 하고 나타 나 는 변수 마다 값 을 계산 합 니 다.
문제 풀이 방향:
데이터 구조 주제 이기 때문에 처음에 자 연 스 럽 게 나 무 를 만 드 는 방법 이 생각 났 다.
방법 을 생각해 본 후에 코드 를 두 드 리 기 시작 했다.나 무 를 만 드 는 코드 를 다 두 드 리 고 결 과 를 계산 하려 고 할 때 이 문 제 는 나 무 를 만 들 필요 가 없고 더 간단 하 다 는 것 을 알 게 되 었 다.
어떤 방법 이 든 문 제 를 푸 는 기본 적 인 사 고 는 표현 식 의 접두사+를 먼저 처리 한 다음 에 왼쪽 에서 오른쪽으로 계산 하면 결 과 를 얻 을 수 있다 는 것 이다.
다음은 비 건 트 리 코드 입 니 다.

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<deque>
#include<vector>
#include<algorithm>

using namespace std;

vector<char>var;
deque<int>que;
const int MAXN = 120;
char str[MAXN];
int val[26]; //     a,b,……z    
int increment;

//            ，    
void Filter(){
    int pos=0;
    for(int i=0; i<strlen(str); ++i){
        if(str[i] != ' '){
            str[pos++] = str[i];
        }
    }
    str[pos] = 0; //        '\0'
}

//      
inline bool havePrefix(int i){
    if(str[i-1]=='+'&&str[i-2]=='+' || str[i-1]=='-'&&str[i-2]=='-')
        return true;
    return false;
}
//      
inline bool haveSuffix(int i){
    if(str[i+1]=='+'&&str[i+2]=='+' || str[i+1]=='-'&&str[i+2]=='-')
        return true;
    return false;
}

void PreProsess(){
    increment = 0;
    while(!que.empty()) que.pop_back();
    var.clear();
    for(int i=0; i<strlen(str); ++i){
        if(str[i]>='a' && str[i]<='z'){
            //    
            var.push_back(str[i]);  //       
            if(i>=2 && havePrefix(i)){
                if(str[i-1]=='+')
                    ++val[str[i]-'a'];
                else
                    --val[str[i]-'a'];
                int n = val[str[i]-'a'];
                que.push_back(n);
                str[i-1]=str[i-2] = ' '; 
            } 
            //    
            else if(i<=strlen(str)-3 && haveSuffix(i)){      
                int n = val[str[i]-'a'];
                que.push_back(n);
                if(str[i+1]=='+'){
                    ++val[str[i]-'a'];
                    --increment;
                }
                else{
                    --val[str[i]-'a'];
                    ++increment;
                }
                str[i+1] = str[i+2] = ' ';
            }
            else {
                int n = val[str[i]-'a'];
                que.push_back(n);
            }
        }
    }
}
int GetSum(){
    for(int i=0; i<strlen(str); ++i){
        if(str[i]=='+' || str[i]=='-'){
            int a=que.front();
            que.pop_front();
            int b=que.front();
            que.pop_front();
            if(str[i]=='+')
                que.push_front(a+b);
            else
                que.push_front(a-b);
        }
    }
    return que.front();
}

void Solve(){
    //  a,b,c……z    
    for(int i=0; i<26; ++i){
        val[i] = i+1;
    }    
    Filter();
    PreProsess();
    int sum = GetSum();
  //  puts(str);
    printf("    value = %d
", sum);
    sort(var.begin(), var.begin()+var.size());
    for(int i=0; i<var.size(); ++i){
        printf("    %c = %d
",var[i], val[var[i]-'a']);
    }
 //   printf("
");
}

int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    while(gets(str)){
        printf("Expression: %s
", str);
        Solve();
    }
    return 0;
}