Problem2

Problem code: AX02

PostFix Instructions to Assembly Code

A very famous company requires a backend for a translator for a Simplified Instructional Computer.
Input to the translator will be arithmetic expressions in postfix form and the output will be assembly language code.
A single register will be present in the target machine along with the following instructions, where the operand is either an identifier or a storage location.

    L -- load the operand into the register
    A -- add the operand to the contents of the register
    S -- subtract the operand from the contents of the register
    M -- multiply the contents of the register by the operand
    D -- divide the contents of the register by the operand
    N -- negate the contents of the register
    ST -- store the contents of the register in the operand location
The contents of the register are replaced with the expression result by an arithmetic operation.
Assembler allocates temporary storage locations for an operand of the form "$n" where n is a single digit.

Input

The input file consists of several legitimate postfix expressions, each on A separate line. Expression operands are single letters and operators are the normaL arithmetic operators (+, -, *, /)

Output

Output must be assembly language code that meets the following requirements:

   1. One instruction per line with the instruction mnemonic separated from the operand (if any) by one blank.
   2. One blank line must separate the assembly code for successive expressions.
   3. The originaL order of the operands must be preserved in the assembly code.
   4. Assembly code must be generated for each operator as soon as it is encountered.
   5. As few temporaries as possible shouL be used (given the above restrictions).
   6. For each operator in the expression, the minimum number of instructions must be generated (given the above restrictions).

Example

Input:
AB+CD+EF++GH+++
AB+CD+-

Output:
L A
A B
ST $1
L C
A D
ST $2
L E
A F
A $2
ST $2
L G
A H
A $2
A $1

L A
A B
ST $1
L C
A D
N
A $1
Author: xpurgate
Date Added: 3-09-2010
Time Limit: 6 sec
Source Limit: 50000 Bytes
Languages: C, CPP 4.0.0-8, CPP 4.3.2, JAVA


Comments

Can someone plz explain the

srish.sriv @ 4 Sep 2010 03:57 AM

Can someone plz explain the difference between the use of subtract and negate. The output of second test case is ambiguous.

What is the rule for

srish.sriv @ 4 Sep 2010 05:32 AM

What is the rule for dividing... I mean division is also ambiguous as subtraction is. In case of subtraction we can negate it and add. But what in the case of division.. Somebody plz reply ..

Even i hav the same problem.

vishal_yash @ 4 Sep 2010 05:55 AM

Even i hav the same problem. second test case is ambiguous .it shud hav subtraction rather than negation. some one plz explain......

We want organizers reply over

kool_kool @ 4 Sep 2010 07:37 AM

We want organizers reply over here!! Zero Submission for this question means something.. Plz explain the question as it is too ambiguous

How many test cases do we

vishal_yash @ 4 Sep 2010 07:47 AM

How many test cases do we need to require as an input for this ques.Some value should be given in the ques. ...

How Can Organizers of

kool_kool @ 4 Sep 2010 08:18 AM

How Can Organizers of "Insomnia" Sleep.. Somebody please take charge!! Clarify the question please

See, for subtraction,

xpurgate @ 4 Sep 2010 10:08 AM

See, for subtraction, negating and adding, saves you a temporary variable. (or subtract and then negate)

 

For division we dont have any instruction to invert the register, so we NEED to have the extra temporary variable.

wat about the number of test

vishal_yash @ 4 Sep 2010 10:28 AM

wat about the number of test cases which shud be pased as input?

how many test cases must be

Zahid1991 @ 4 Sep 2010 01:48 PM

how many test cases must be taken as input??

For Division, do we need to

ankul_iiita @ 4 Sep 2010 06:37 PM

For Division, do we need to load the register value in a temporary and load the previous temporary in register and then divide? Are we allowed something like L $x ??

Those who have solved the

root5 @ 4 Sep 2010 09:22 PM

Those who have solved the question please explain  what we have to do to subtract,i mean what the use of S..if we can negate too and then add

when we have to terminate the

root5 @ 4 Sep 2010 09:25 PM

when we have to terminate the input

@satyarth terminate it when

dabbcomputers @ 5 Sep 2010 12:39 AM

@satyarth terminate it when eof reached like when gets(str)==null or scanf(%s",str)==-1

@admin can you pls send me

dabbcomputers @ 5 Sep 2010 12:56 AM

@admin can you pls send me the test case file for this problem i got "WA" every time and could find any error.

there is no problem in the

mayuresh.1590 @ 5 Sep 2010 01:22 PM

there is no problem in the question.

or test data

mayuresh.1590 @ 5 Sep 2010 01:22 PM

or test data

^ there mat not be, but some

f03nix @ 5 Sep 2010 02:28 PM

^ there mat not be, but some of us would like to still test our code to understand what went wrong. We can't do it here can we ?

in C++ you could have used,

xpurgate @ 6 Sep 2010 01:59 AM

in C++ you could have used, while(cin>>whatever) i guess, there is no need to enter data character by character, the string doesnt have spaces...

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions