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\n", sum);
    sort(var.begin(), var.begin()+var.size());
    for(int i=0; i<var.size(); ++i){
        printf("    %c = %d\n",var[i], val[var[i]-'a']);
    }
 //   printf("\n");
}

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

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double