dDescription:

　

Write a program that performs basic arithmetic, including addition, subtract, multiplication, and division, of large integers. Large integers are numbers that are significantly larger than those ordinarily used in our life. They are widely used in many fields such as cryptography. The program is required to handle signed decimal numbers with more than 15 digits and behave like a calculator with the ability to deal with complex arithmetic expressions, e.g. (A+B)*C/D. If the result of integer division is a real number a.b, just truncate b so that the result is still an integer (like the definition of '/' for integers in C). Note that the program is not allowed to use the floating-point instructions and the ASCII and packed/unpacked decimal arithmetic instructions introduced in Chapter 8, that is, AAA, AAS, AAM, AAD, DAA and DAS. The I/O of your program is

　

Input: arithmetic expressions with $ as the end character.  For example, (A+B)*C/D$.

          The signed numbers (i.e., A, B, C and D) may be more than 15 decimal digits.

Output: the signed answer of the expression

　

Hint: To evaluate an arithmetic expression, one possible solution is to use two stacks: one for numbers (number stack) and the other for operators (operator stack). Going from left to right, if you see a number, push it on the number stack. If you see an operator x,

        while the top of the operator stack, y, holds an operator of equal or higher precedence (compared with x)

        begin
                pop operator y 
                pop the top two values from the number stack and apply operator  y to them

                push the result on the number stack
        end

        push operator x on the operator stack
At the end, perform any remaining operations on both stacks

　

To handle parentheses, when you see a left parenthesis, (, treat it as a low-priority operator, and just put it on the operator stack. When you see a right parenthesis , ), perform all the operations on the operator stack until you reach the corresponding left parenthesis; then remove the left parenthesis.

　

For example, suppose the input is 1+2*3-5/(3+4)$ Your program might scan it from left to right and evaluate the expression by the following steps, where nstack stands for the number stack, pstack stands for the operator stack, and pr(op)=operator op's preference.

　

    (nstack: empty; pstack: empty)

    1 : push 1 on nstack  (nstack: 1; pstack: empty)
    + : push + on pstack (nstack: 1; pstack: +)
    2:  push 2 on nstack  (nstack: 1,2; pstack: +)
    * : because pr(+)<pr(*), push * on pstack (nstack: 1,2; pstack: +,*)

    3:  push 3 on nstack  (nstack: 1,2,3; pstack: +,*)
    -:  because pr(*)>pr(-), pop * from pstack, pop 3, 2 from nstack, compute 2*3=6, push 6 on nstack (nstack: 1,6; pstack: +)

        because pr(+)>pr(-) (while loop),  pop + from pstack, pop 6, 1 from nstack, compute 1+6=7, push 7 on nstack (nstack: 7; pstack: empty)

        push - on pstack  (nstack: 7; pstack: -)

    5: push 5 on nstack  (nstack: 7,5; pstack: -)

     /: because pr(-)<pr(/), push / on pstack (nstack: 7,5; pstack: -,/)

     (: just push '(' on pstack (nstack: 7,5; pstack: -,/,'(')

    3: push 3 on nstack  (nstack: 7,5,3; pstack: -,/,'(')

    +: because pr('(')<pr(+), push + on pstack (nstack: 7,5,3; pstack: -,/,'(',+)

    4: push 4 on nstack (nstack: 7,5,3,4; pstack: -,/,'(',+)

     ): pop + from pstack, pop 4,3 from nstack, compute 3+4=7, push 7 on nstack, pop '(' from pstack (nstack: 7,5,7; pstack: -,/)

    $:  end of the expression, pop / from pstack, pop 7,5 from nstack, compute 5/7=0, push 0 on nstack (nstack: 7,0; pstack: -)

        pop - from pstack, pop 0,7 from nstack, compute 7-0=7, push 7 on nstack (nstack: 7; pstack: empty)

        the answer is 7 (the one on nstack)

         

nn

Deadline: Due on 12/14, beginning of class

n

　

Submission: Closed.