# Optimize Compiler for simple Reverse Polish Notation Programming Language

## Description

Imaginary programming language (IPL) uses Polish Reverse Notation. It has the following commands:

• i -- input number and push it to the stack
• o -- non-destructive output top of the stack (number stays on the stack)
• d -- discard top of stack
• integer number -- push this number to the stack
• +-* -- pop two numbers from the stack, perform corresponding operation and push back the result. There is no division in IPL.

IPL works only with integers and is used for simple calculations. An IPL program is written on one line and separated by spaces. Empty string is a valid IPL program.

IPL Program:

i i + o


Inputs two numbers, adds them together and outputs the result.

Input numbers and integers that can be pushed to stack are in range [-999, 999], however output can be any. If your language do not support big numbers it is okay though.

## Input/output format

You may choose any input/output format as long as it clear to understand and read/write: string, list, tokens etc.

You are given some IPL program, you need to optimize it (reduce length):

i 12 + 3 + o d 2 3 + d


After optimization will become

i 15 + o


You do not have to preserve stack state, but amount of inputs and outputs and their order should match for the original and optimized program.

So IPL program:

-40 i * 2 * o i + 3 1 + o i 2 *


After optimisation will become

i -80 * o i 4 o i


or

-80 i * o i 4 o i


(note that you have to save all inputs, even if they are irrelevant).

There should be no hardcoding for test cases, code should work on any arbitrary IPL program and produce shortest possible IPL program that meets the requirements.

## Scoring

Default code-golf scoring.

UPDATE: changed scoring to pure code golf scoring, as per @Sanchises suggestion.

## Test cases:

Input:

(empty string)


Possible output:

(empty string)


Input:

i 4 * 2 + 3 * 6 - o


Possible output:

i 12 * o


Input:

1 1 + o


Possible output:

2 o


Input:

i 2 + 3 + o d 2 3 + d


Possible output:

i 5 + o


Input:

-40 i * 2 * o i + 3 1 + o i 2 *


Possible output:

-80 i * o i 4 o i


Input:

i i 1 + i 1 + i 1 + i 1 + d d d d o


Possible output:

i i i i i d d d d o


Input:

i i i 0 * * * o


Possible output:

i i i 0 o


Input:

i i i 1 * * * o


Possible output:

i i i * * o


Input:

i 222 + i 222 - + o


Possible output:

i i + o


Input:

i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o


Possible output:

i i i i i o 1 o


Input:

i 1 + 2 * 1 + o


Possible output:

i 2 * 3 + o


Input:

1 1 + o i 2 + 3 + o d 2 3 + d 4 i * 2 * o i + 3 1 + o i 2 * i i 1 + i 1 + i 1 + i 1 + d d d d o i i i 0 * * * o i i i 1 * * * o i 2 + i 2 - + o i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o


Possible output:

2 o i 5 + o 8 i * o i 4 o i i i i i i d d d d o i i i 0 o i i i * * * o i i + o i i i i i o 1 o

• A question: can you simplify i i d o to i o i (the input is in order and the output is in order) or should you not simplify it? (the set of input and outputs should be in order) – Sanchises Aug 1 '18 at 12:01
• @Sanchises no, inputs and outputs should be in order. If original program inputs 2 numbers before outputing anything optimised should do the same. – Андрей Ломакин Aug 1 '18 at 12:03
• Welcome to PPCG! Nice first Challenge! – Luis felipe De jesus Munoz Aug 1 '18 at 13:49
• May there be d or o when stack is empty? – user202729 Aug 2 '18 at 2:03
• From review queue, I do not think this challenge is unclear. If you do, please comment about why. – mbomb007 Aug 2 '18 at 14:17