欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVa 327 - Evaluating Simple C Expressions

程序员文章站 2024-03-19 09:17:04
...
UVa 327 - Evaluating Simple C Expressions 327-Evaluating Simple C Expressions 3763
30.56%
1145
70.66%
题目链接:


样例输入:
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;
}