Created
May 7, 2025 17:13
-
-
Save jeffersonmourak/a2e2411185f08a84673fffb4ab5068ec to your computer and use it in GitHub Desktop.
Parser from infix notation to postfix notation.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| type Ops = "*" | "+" | "-" | "/"; | |
| type Postfix = (number | Ops)[]; | |
| // const infix = "(2 + 8 / 2 * (1 + 2) - 2)"; | |
| const infix = "(12 + 8 / 2 * (1 + 2) - 14)"; | |
| const precedence: Record<string, number> = { | |
| "+": 1, | |
| "-": 1, | |
| "*": 2, | |
| "/": 2, | |
| }; | |
| const isOperator = (char: string): char is Ops => { | |
| return Object.keys(precedence).includes(char); | |
| }; | |
| function infixToPostfix(infix: string): Postfix { | |
| const stack: string[] = []; | |
| const output: Postfix = []; | |
| for (let i = 0; i < infix.length; i++) { | |
| const char = infix[i]; | |
| if (char === " ") continue; | |
| if (char === "(") { | |
| stack.push(char); | |
| continue; | |
| } | |
| if (char === ")") { | |
| while (stack.length && stack[stack.length - 1] !== "(") { | |
| output.push(stack.pop() as Ops); | |
| } | |
| stack.pop(); | |
| continue; | |
| } | |
| if (isOperator(char)) { | |
| while ( | |
| stack.length && | |
| precedence[stack[stack.length - 1]] >= precedence[char] | |
| ) { | |
| output.push(stack.pop() as Ops); | |
| } | |
| stack.push(char); | |
| continue; | |
| } | |
| if (!isNaN(Number(char))) { | |
| let num = char; | |
| while (i + 1 < infix.length && !isNaN(Number(infix[i + 1]))) { | |
| num += infix[++i]; | |
| } | |
| output.push(Number(num)); | |
| continue; | |
| } | |
| throw new Error(`Invalid character: ${char}`); | |
| } | |
| return output; | |
| } | |
| console.log(infixToPostfix(infix)); // --> [ 12, 8, 2, "/", 1, 2, "+", "*", "+", 14, "-" ] | |
| console.log(pp(infixToPostfix(infix))); // --> [ 10 ] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment