2012年10月15日

UVa 112 - Tree Summing


#include <cstdio>
#include <stack>
using std::stack;

int main() {
  int ans;
  while (scanf("%d", &ans) == 1) {
    int l = 0, r = 0, num = 0, sum = 0;
    stack<int> tree;
    char c, old[4] = {0};
    bool flag = 0, start = 0, neg = 0;
    while (!start || l != r) {
      c = getchar();
      switch (c) {
        case '(':
          l++;
          if (start && old[2] != ')') {
            if (neg) num *= -1;
            sum += num;
            tree.push(num);
            num = 0;
            neg = 0;
          }
          old[0] = old[1];
          old[1] = old[2];
          old[2] = c;
          start = 1;
          break;
        case ')':
          r++;
          if (old[2] != '(' && tree.size()) {
            sum -= tree.top();
            tree.pop();
          } else if (old[0] == '(' && old[1] == ')' && old[2] == '(' && sum == ans) {
            flag = 1;
          }
          old[0] = old[1];
          old[1] = old[2];
          old[2] = c;
          break;
        case '-':
          neg = 1;
        case ' ':
        case '\n':
          break;
        default:
          num = num * 10 + c - '0';
      }
    }
    if (flag) puts("yes");
    else puts("no");
  }
  return 0;
}

沒有留言:

張貼留言