# Infix→Postfix Assembler

Two things in one project. First, a templated stack class written from scratch as a linked list. Second, a small toolchain that uses the stack to convert a parenthesized infix expression into postfix, then walks the postfix form to emit mock assembly instructions.

## The stack

`stack<T>` in `stack.hpp` is a singly linked list of `Node<T>`, with the top of stack as the head. It is a header-only template, so there is nothing to compile on its own. The interesting part is the resource management: it has a copy constructor that deep-copies the chain, a destructor that pops until empty, a constant-time `swap`, and copy-and-swap assignment. `push`, `pop`, `top`, and `empty` are the usual operations, and `full` always returns false because a linked stack never fills.

The stack stores `String` values from the [Custom String](Custom-String.md) project, so this project reuses that class. The Makefile and CI both add `-I ../string` and link the String object file.

## Stage one: infix to postfix

The input format is fully parenthesized infix, one expression per line, tokens separated by spaces, ending with `;`. For example:

```
( AX + ( B * C ) ) ;
( ( A + B ) * ( C + E ) ) ;
```

Because every operation is wrapped in its own parentheses, the conversion does not need an operator-precedence table. `infixToPostfix` scans left to right and pushes every operand and operator onto the stack. On a closing paren it pops exactly three things (right operand, operator, left operand) and pushes back the postfix chunk `left right operator`. Open parens are skipped. At the end it drains the stack into the result.

```mermaid
flowchart TD
    A[Read next token from infix] --> B{Token type?}
    B -- "open paren (" --> A
    B -- "close paren )" --> C[Pop right, then operator, then left]
    C --> D[Push left + right + operator back]
    D --> A
    B -- "operand or operator" --> E[Push the single token]
    E --> A
    B -- "space" --> A
    A --> F{End of input?}
    F -- no --> A
    F -- yes --> G[Pop everything, prepend to postfix]
    G --> H[Return postfix string]
```

## Stage two: postfix to assembly

`postfixToAssembly` evaluates the postfix form on a second stack to produce three-address instructions. Operands get pushed. When an operator comes up, it pops the two operands, emits one instruction into a temporary register, and pushes the temporary back so later operators can use it. The opcode comes from `makeAssembly`:

| Operator | Opcode |
| --- | --- |
| `+` | `AD` |
| `-` | `SB` |
| `*` | `MU` |
| `/` | `DV` |

So `A B +` turns into `AD A, B, TMP`. The `assembler` driver writes both the infix, the postfix, and the emitted instructions to `output.txt`.

## Build and run

```sh
cd assembler
make tests        # stack assertion suite
make postfix      # infix -> postfix only
make assembler    # full pipeline, writes output.txt
./assembler data3-1.txt
```

The course Makefile uses `clang++ -std=c++17`. Under CI everything builds with `g++ -std=c++11 -I ../string`.

## Notes and limits

The converter depends on full parenthesization. A bare expression like `A + B * C` would not convert correctly because there is no precedence handling; a real shunting-yard pass would fix that. The `test_generic_*` files here are blank course templates and CI skips them. One detail worth flagging: `postfixToAssembly` currently emits operands as it pops, so for the single-temporary scheme it assumes a left-to-right operand order that matches the parenthesized inputs in the data files.