2013年8月18日

UVa 11954 - Binary Calculator

#include <cstdio>
#include <sstream>
#include <string>
#include <vector>
#define PB push_back
using namespace std;

inline void removeZero(string & s) {
  while (s[0] == '0' && s.length() > 1) {
    s.erase(s.begin());
  }
}

int main() {
  char s[1005];
  gets(s);
  int T, C = 1;
  sscanf(s, "%d", &T);
  while (T--) {
    gets(s);
    istringstream ss(s);
    string word;
    vector<string> exp;
    while (ss >> word) {
      removeZero(word);
      exp.PB(word);
    }
    for (int i = exp.size() - 1; i > 0; i--) {
      if (exp[i - 1] == "not") {
        for (int j = 0; exp[i][j]; j++) {
          exp[i][j] = (exp[i][j] == '0') ? '1' : '0';
        }
        removeZero(exp[i]);
        exp.erase(exp.begin() + i - 1);
      } else if (exp[i - 1] == "shl") {
        exp[i] += "0";
        exp.erase(exp.begin() + i - 1);
      } else if (exp[i - 1] == "shr") {
        if (exp[i].length() > 1) {
          exp[i].erase(exp[i].begin() + exp[i].length() - 1);
        } else {
          exp[i] = "0";
        }
        exp.erase(exp.begin() + i - 1);
      }
    }
    for (int i = 1; i < exp.size(); i += 2) {
      int l1 = exp[i - 1].length(), l2 = exp[i + 1].length();
      int l = l1 > l2 ? l1 : l2;
      exp[i - 1] = string(l - l1, '0') + exp[i - 1];
      exp[i + 1] = string(l - l2, '0') + exp[i + 1];
      if (exp[i] == "xor") {
        for (int j = 0; exp[i + 1][j]; j++) {
          exp[i + 1][j] = (exp[i + 1][j] != exp[i - 1][j]) ? '1' : '0';
        }
      } else if (exp[i] == "and") {
        for (int j = 0; exp[i + 1][j]; j++) {
          exp[i + 1][j] = (exp[i + 1][j] == '1' && exp[i - 1][j] == '1') ? '1' : '0';
        }
      } else if (exp[i] == "or") {
        for (int j = 0; exp[i + 1][j]; j++) {
          exp[i + 1][j] = (exp[i + 1][j] == '1' || exp[i - 1][j] == '1') ? '1' : '0';
        }
      }
    }
    string ans = exp.back();
    removeZero(ans);
    printf("Case %d: %s\n", C++, ans.c_str());
  }
  return 0;
}

沒有留言:

張貼留言