prithivMLmods/Coder-Stat

1 2<H1>Calculation of Expressions</H1>3 4<P>Write a program to calculate values of arithmetic expressions which may5involve complex numbers. Details of the expressions are described below.</P>6 7<P>In this problem, basic elements of expressions are 8non-negative integer numbers and9the special symbol &quot;<TT>i</TT>&quot;. Integer numbers are  sequences10of digits of arbitrary length and are in decimal notation. &quot;<TT>i</TT>&quot; denotes the11unit imaginary number <I>i</I>, i.e. <I>i</I><SUP> 2</SUP> = -1.</P>12 13<P>Operators appearing in expressions are <TT>+</TT> (addition), <TT>-</TT>14(subtraction), and <TT>*</TT> (multiplication). Division is excluded from15the repertoire of the operators. All three operators are only used as binary16operators. Unary plus and minus operators (e.g., <TT>-100</TT>) are also17excluded from the repertoire. Note that the multiplication symbol <TT>*</TT>18may not be omitted in any case. For example, the expression 1+3<I>i</I>19in mathematics should be written as <TT>1+3*i</TT>.</P>20 21<P>Usual formation rules of arithmetic expressions apply. Namely, (1) The22operator <TT>*</TT> binds its operands stronger than the operators <TT>+</TT>23and <TT>-</TT>. (2) The operators <TT>+</TT> and <TT>-</TT> have the same24strength in operand binding. (3) Two operators of the same strength bind25from left to right. (4) Parentheses are used to designate specific order26of binding.</P>27 28<P>The consequence of these rules can easily be understood from the following29examples.</P>30 31<BLOCKQUOTE>32  <BLOCKQUOTE>33    <P>(1) <TT>3+4*5</TT> is <TT>3+(4*5)</TT>, not <TT>(3+4)*5</TT><BR>34    (2) <TT>5-6+7</TT> is <TT>(5-6)+7</TT>, not <TT>5-(6+7)</TT><BR>35    (3) <TT>1+2+3</TT> is <TT>(1+2)+3</TT>, not <TT>1+(2+3)<BR>36    </TT></P>37  </BLOCKQUOTE>38</BLOCKQUOTE>39 40<P>Your program should successively read expressions, calculate them and41 print their results. Overflow should be detected.</P>42 43<P>Whenever an abnormal value is yielded as a result of applying an operator44appearing in the given expression, 45your program should report that the calculation failed due to overflow. 46By &quot;an abnormal value&quot;, we mean a value 47whose real part or imaginary part is48greater than 10000 or less than -10000. Here are examples:</P>49 50<P ALIGN=CENTER><TABLE BORDER="1" CELLSPACING="2" CELLPADDING="0">51<TR>52<TD WIDTH="50%"><TT>10000+1+(0-10)</TT></TD>53<TD WIDTH="50%">overflow, not 9991</TD></TR>54<TR>55<TD WIDTH="50%"><TT>(10*i+100)*(101+20*i)</TT></TD>56<TD WIDTH="50%">9900+3010<I>i </I>, not overflow</TD></TR>57<TR>58<TD WIDTH="50%"><TT>4000000-4000000</TT></TD>59<TD WIDTH="50%">overflow, not 0</TD></TR>60</TABLE>61</P>62 63<P>Note that the law of associativity does not necessarily hold in this64problem.  For example, in the first example, 65overflow is detected by interpreting66the expression as <TT>(10000+1)+(0-10)</TT> following the binding rules,67whereas overflow could not be detected 68if you interpreted it as <TT>10000+(1+(0-10))</TT>.69Moreover, overflow detection should take place for resulting value of each70operation.</P>71 72<P>In the second example, a value which exceeds 10000 appears73in the calculation process of one multiplication 74if you use the mathematical rule</P>75 76<BLOCKQUOTE>77  <P>(<I>a</I>+<I>b i</I>)(<I>c</I>+<I>d</I> <I>i</I>)=(<I>ac</I>-<I>bd</I>)+(<I>ad</I>+<I>bc</I>)<I>i78  </I>.</P>79</BLOCKQUOTE>80 81<P>But the yielded result 9900+3010<I>i </I>does not contain any number82which exceeds 10000 and, therefore, overflow should not be reported.</P>83 84<P></P>85 86<H2>Input</H2>87 88<P>A sequence of lines each of which contains an expression is given as89input. Each line consists of less than 100 characters and does not contain90any blank spaces. You may assume that all expressions given in the sequence91are syntactically correct.</P>92 93<H2>Output</H2>94 95<P>Your program should produce output for each expression line by line.96If overflow is detected, output should be 97a character string &quot;<TT>overflow</TT>&quot;.98Otherwise, output should be the resulting value of calculation99in the following fashion.</P>100 101<UL>102  <LI><TT>0</TT> , if the result is 0+0<I>i</I>.103  <LI><TT>-123</TT> , if the result is -123+0<I>i</I>.104  <LI><TT>45i</TT> , if the result is 0+45<I>i</I>.105  <LI><TT>3+1i</TT> , if the result is 3+<I>i</I>.106  <LI><TT>123-45i</TT> , if the result is 123-45<I>i</I>.107</UL>108 109<P>Output should not contain any blanks, surplus <TT>0</TT>,110<TT>+</TT>, or <TT>-</TT>.</P>111 112<H2>Sample Input</H2>113 114<pre>115(1-10*i)+00007+(3+10*i)1163+4*i*(4+10*i)117(102+10*i)*(99+10*i)1182*i+3+9999*i+4119</pre>120 121<H2>Output for the Sample Input</H2>122 123<pre>12411125-37+16i1269998+2010i127overflow128</pre>129 130