Tech Deep Dive

How the Infix Conversion Works

This page explains every major part of the Infix Conversion project. All code shown is the real code from this project.

🧠 What is the Shunting Yard Algorithm?

The Shunting Yard algorithm, invented by Edsger Dijkstra, is a method for parsing mathematical expressions specified in infix notation. It can be used to produce output in Reverse Polish Notation (Postfix) or Prefix notation. The algorithm uses a stack to hold operators and pushes operands directly to the output.

Infix:
A
+
B
Postfix:
A
B
+ ✨

1. Tokenization & Input Prep

First, the user's input string is broken down into a list of meaningful tokens (operands, operators, parentheses) using a regular expression. This gives us an array of items to iterate through. 

// From script.js — Tokenizer helper
const tok = (e) => e.match(/[a-zA-Z0-9]+|[\+\-\*\/\^\(\)]/g) || [];

let t = tok(exp);

2. Prefix Pre-processing (Prefix Only)

If doing Prefix conversion (via InfixToPrefix), we process the expression backwards. We reverse the token array and swap left and right parentheses, then run the algorithm. 

// From InfixToPrefix() — Reverse tokens & swap parenthesis
t = t.reverse().map((c) => (c === "(" ? ")" : c === ")" ? "(" : c));

3. The Core Loop: Operands & Parentheses

We initialize an out array for results and an ops stack for operations. As we iterate over each token:
• Operands (letters/numbers) are pushed directly to the output.
• Open Parentheses ( are pushed to the stack.
• Close Parentheses ) trigger popping from the stack to the output until the matching open parenthesis is found. 

let out = [], ops = [];
t.forEach((c) => {
  switch (true) {
    case isOp(c):
      out.push(c); // Operand straight to output
      break;
      
    case c === "(":
      ops.push(c); // Open parenthesis to stack
      break;
      
    case c === ")":
      // Pop until we discover '('
      while (ops.length && ops[ops.length - 1] !== "(")
        out.push(ops.pop());
      ops.pop(); // Discard the '(' itself
      break;

4. The Core Loop: Operators & Precedence

If the token falls into the default case, it must be an operator (like +, *, ^). We check its precedence against the operator at the top of the stack. Because Prefix evaluates right-to-left for powers (associativity), its conditional check differs slightly from Postfix. 

    default:
      while (ops.length && ops[ops.length - 1] !== "(") {
        let top = ops[ops.length - 1];
        
        // Postfix Check:
        // if (p[top] > p[c] || (p[top] === p[c] && c !== "^"))

        // Prefix Check:
        // if (p[top] > p[c] || (p[top] === p[c] && c === "^"))
          
        if (cond) out.push(ops.pop());
        else break;
      }
      ops.push(c); // Finally push the new operator
      break;
  }
});

5. Final Polish & Output

Once the loop is finished, we empty any remaining operators from the stack into the output array. If doing Prefix, this is where we reverse the entire output array back to normal so it reads correctly. The user sees the final joined string on the screen! 

// Flush remaining operators to the output
while (ops.length) out.push(ops.pop());

// Postfix finish:
// return out.join(" ");

// Prefix finish:
// return out.reverse().join(" ");

📋 Operations Summary

Phase Time Complexity
Tokenization O(n)
Iteration O(n)
Array Reverse (Prefix) O(n)

⚙️ Reference Algorithm Flowcharts

1. Application Flow

%%{init: {'flowchart': {'curve': 'linear'}}}%% flowchart LR Start([Start]) --> Expr[/Expression/] Expr --> RmWS[Remove Whitespace
in Expression] RmWS --> Op[Operator
Operand] Op --> PreFix[function
InfixtoPrefix(expression)] Op --> PostFix[function
InfixtoPostfix(expression)] PostFix --> Print[/Infix, Prefix, Postfix/] PreFix --> Print Print --> End([End]) style Start fill:#111,stroke:#fff,color:#fff style Expr fill:#111,stroke:#fff,color:#fff style RmWS fill:#111,stroke:#fff,color:#fff style Op fill:#111,stroke:#fff,color:#fff style Print fill:#111,stroke:#fff,color:#fff style End fill:#111,stroke:#fff,color:#fff style PreFix fill:#2b7c12,stroke:#fff,color:#fff style PostFix fill:#0075c4,stroke:#fff,color:#fff

2. getPrecedence Mapping

%%{init: {'flowchart': {'curve': 'stepAfter'}}}%% flowchart TD Start([Start_getPrecedence]) --> Check{Operator is?} Check -->|**| Ret3[return 3] Check -->|*, /| Ret2[return 2] Check -->|+, -| Ret1[return 1] Check -->|else| Ret0[return 0] Ret3 --> End([End_getPrecedence]) Ret2 --> End Ret1 --> End Ret0 --> End style Start fill:#111,stroke:#fff,color:#fff style Check fill:#111,stroke:#fff,color:#fff style Ret3 fill:#111,stroke:#fff,color:#fff style Ret2 fill:#111,stroke:#fff,color:#fff style Ret1 fill:#111,stroke:#fff,color:#fff style Ret0 fill:#111,stroke:#fff,color:#fff style End fill:#111,stroke:#fff,color:#fff linkStyle default stroke:#fff

3. Start_InfixtoPostfix Loop

%%{init: {'flowchart': {'curve': 'linear'}}}%% flowchart TD Start([Start_InfixtoPostfix]) --> InitS[/Stack = []/] InitS --> InitP[/PostFix = []/] InitP --> Expr[/Expression/] Expr --> Idx[/Index = 0/] Idx --> CharGet[char = expression
charAt(index)] CharGet --> OpCheck{Operand is?} %% Main Loop Branching OpCheck -->|char = (| TrueOpen[Postfix push(char)] OpCheck -->|False
char = )| TrueClose[Postfix push(Stack.pop\(\))] OpCheck -->|False
Operator?| TrueOp[check priority &&
insert char to Postfix] OpCheck -->|False
index < Expression.length| TrueEnd{ } %% Loop Connecting Back TrueOpen --> LoopEnd[/index++/] TrueClose --> CloseCheck{Stack.top\(\) == \(?} CloseCheck -->|False| TrueClose CloseCheck -->|True| LoopEnd TrueOp --> PushStack[Stack.push\(\)] PushStack --> LoopEnd TrueEnd -->|True| CharGet LoopEnd --> OpCheck %% The diagram styling style Start fill:#0075c4,stroke:#fff,color:#fff classDef generic fill:#111,stroke:#fff,color:#fff class InitS,InitP,Expr,Idx,CharGet,OpCheck,TrueOpen,TrueClose,TrueOp,TrueEnd,LoopEnd,CloseCheck,PushStack generic linkStyle default stroke:#fff
Workshop: Infix Conversion — CSI105T Data Structures · Author: 68037294 Raksit Phothong