/* @file 3.cc @brief Solves "Calcuration of Expressions" ( http://www.acm-japan.org/past-icpc/domestic1998/problem3.htm ) @author Yuta Kitamura @date 2005-04-27 */ // start 13:02 // end 15:03 #include #include #include #include #include #include using std::cout; using std::cin; using std::endl; using std::ostream; using std::vector; using std::string; using std::istringstream; using std::getline; using std::find_if; typedef unsigned int uint; class Complex { int r_, i_; bool overflow_; public: Complex() : r_(0), i_(0), overflow_(false) {} Complex(int r, int i) : r_(r), i_(i), overflow_(false) { if (r < -10000 || 10000 < r || i < -10000 || 10000 < i) overflow_ = true; return; } Complex(const Complex& c) : r_(c.r_), i_(c.i_), overflow_(c.overflow_) {} friend ostream& operator<< (ostream& ost, const Complex& c); friend Complex operator+ (const Complex& lhs, const Complex& rhs); friend Complex operator- (const Complex& lhs, const Complex& rhs); friend Complex operator* (const Complex& lhs, const Complex& rhs); }; ostream& operator<< (ostream& ost, const Complex& c) { if (c.overflow_) ost << "overflow"; else if (c.r_ == 0 && c.i_ == 0) ost << 0; else if (c.i_ == 0) ost << c.r_; else if (c.r_ == 0) { ost << c.i_ << 'i'; } else { ost << c.r_; if (c.i_ > 0) ost << '+'; ost << c.i_ << 'i'; } return ost; } Complex operator+ (const Complex& lhs, const Complex& rhs) { Complex c; if (lhs.overflow_ || rhs.overflow_) c.overflow_ = true; else { c.r_ = lhs.r_ + rhs.r_; c.i_ = lhs.i_ + rhs.i_; if (c.r_ < -10000 || 10000 < c.r_ || c.i_ < -10000 || 10000 < c.i_) c.overflow_ = true; } return c; } Complex operator- (const Complex& lhs, const Complex& rhs) { Complex c; if (lhs.overflow_ || rhs.overflow_) c.overflow_ = true; else { c.r_ = lhs.r_ - rhs.r_; c.i_ = lhs.i_ - rhs.i_; if (c.r_ < -10000 || 10000 < c.r_ || c.i_ < -10000 || 10000 < c.i_) c.overflow_ = true; } return c; } Complex operator* (const Complex& lhs, const Complex& rhs) { Complex c; if (lhs.overflow_ || rhs.overflow_) c.overflow_ = true; else { c.r_ = lhs.r_ * rhs.r_ - lhs.i_ * rhs.i_; c.i_ = lhs.r_ * rhs.i_ + lhs.i_ * rhs.r_; if (c.r_ < -10000 || 10000 < c.r_ || c.i_ < -10000 || 10000 < c.i_) c.overflow_ = true; } return c; } enum TokenType { NUM, ADD, SUB, MUL, OPA, CPA }; struct Token { TokenType type; Complex num; }; vector tokenize(const string& s) { vector v; string buf; string::size_type i = 0; while (i <= s.length()) { char c; if (i == s.length()) c = '\0'; else c = s[i]; //cout << c << endl; if ('0' <= c && c <= '9') buf.append(1, c); else if (c == 'i') { Token t; t.type = NUM; t.num = Complex(0, 1); v.push_back(t); } else { Token t; if (!buf.empty()) { istringstream iss(buf); int r; iss >> r; t.type = NUM; t.num = Complex(r, 0); v.push_back(t); buf.clear(); } t.num = Complex(); if (c == '+') t.type = ADD; else if (c == '-') t.type = SUB; else if (c == '*') t.type = MUL; else if (c == '(') t.type = OPA; else if (c == ')') t.type = CPA; else if (c != '\0') assert(false); if (c != '\0') v.push_back(t); } ++i; } return v; } bool isAddToken(Token t) { return t.type == ADD; } bool isSubToken(Token t) { return t.type == SUB; } bool isMulToken(Token t) { return t.type == MUL; } bool isOPaToken(Token t) { return t.type == OPA; } bool isCPaToken(Token t) { return t.type == CPA; } Complex evaluate(vector tokens) { /* cout << "["; for (vector::iterator i = tokens.begin(); i != tokens.end(); ++i) { if (i != tokens.begin()) cout << ", "; cout << "(" << i->type << ", " << i->num << ")"; } cout << "]" << endl; */ if (tokens.size() == 0) return Complex(); else if (tokens.size() == 1) return tokens[0].num; vector::iterator it = find_if(tokens.begin(), tokens.end(), isOPaToken); if (it != tokens.end()) { vector::iterator itEnd = it + 1; uint depth = 0; while (itEnd != tokens.end()) { if (isOPaToken(*itEnd)) ++depth; else if (isCPaToken(*itEnd)) { if (depth == 0) break; else --depth; } ++itEnd; } Token t; t.type = NUM; t.num = evaluate(vector(it + 1, itEnd)); tokens.erase(it + 1, itEnd + 1); *it = t; return evaluate(tokens); } it = find_if(tokens.begin(), tokens.end(), isMulToken); if (it != tokens.end()) { Token lhs = *(it - 1); Token rhs = *(it + 1); assert(lhs.type == NUM); assert(rhs.type == NUM); Token t; t.type = NUM; t.num = lhs.num * rhs.num; *(it - 1) = t; tokens.erase(it, it + 2); return evaluate(tokens); } vector::iterator itA = find_if(tokens.begin(), tokens.end(), isAddToken), itS = find_if(tokens.begin(), tokens.end(), isSubToken); if (itA != tokens.end() || itS != tokens.end()) { if (itA < itS) { Token lhs = *(itA - 1); Token rhs = *(itA + 1); assert(lhs.type == NUM); assert(rhs.type == NUM); Token t; t.type = NUM; t.num = lhs.num + rhs.num; *(itA - 1) = t; tokens.erase(itA, itA + 2); return evaluate(tokens); } else { Token lhs = *(itS - 1); Token rhs = *(itS + 1); assert(lhs.type == NUM); assert(rhs.type == NUM); Token t; t.type = NUM; t.num = lhs.num - rhs.num; *(itS - 1) = t; tokens.erase(itS, itS + 2); return evaluate(tokens); } } assert(false); return Complex(); } int main() { while (cin) { string line; getline(cin, line); if (!cin) break; vector tokens(tokenize(line)); if (tokens.empty()) continue; Complex c(evaluate(tokens)); cout << c << endl; } return 0; }