Parsing/Shunting-yard algorithm: Difference between revisions

{{trans|Java}}

-V ops = ‘-+/*^’

V sb = ‘’

V infix = ‘3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3’

print(‘infix: ’infix)

{{out}}

=={{header|8th}}==

\ https://en.wikipedia.org/wiki/Shunting-yard_algorithm

"Expected: \n" . "3 4 2 * 1 5 - 2 3 ^ ^ / +" . cr

bye

{{out}}

<pre>NUMBER 3

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}

# parses s and returns an RPN expression using Dijkstra's "Shunting Yard" algorithm #

# s is expected to contain a valid infix expression containing single-digit numbers and single-character operators #

print( ( "result: ", parse( "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" ), newline ) )

{{out}}

<pre>

=={{header|AutoHotkey}}==

{{works with|AutoHotkey_L}}

#NoEnv

Space(n){

return n>0 ? A_Space Space(n-1) : ""

;Output

<pre style="height:30ex;overflow:scroll;">Testing string '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'

=={{header|C}}==

Requires a functioning ANSI terminal and Enter key.

#include <regex.h>

#include <stdio.h>

return 0;

;Output:

=={{header|C sharp}}==

{{works with|C sharp|7.0}}

using System.Collections.Generic;

using System.Linq;

void Print(string action) => Console.WriteLine("{0,-4} {1,-18} {2}", action + ":", $"stack[ {string.Join(" ", stack.Reverse())} ]", $"out[ {string.Join(" ", output)} ]");

}

{{out}}

<pre>

clang++ -Wall -pedantic-errors -O3 -std=c++17 a.cpp

#include <iostream>

#include <regex>

std::cerr << "error: " << e.what() << "\n";

return 1;

{{out}}

<pre>C:\Users\JRandom\cpp> a.exe 3 + 4 * 2 / ( 1 - 5 ) ^^ 2 ^^ 3

Here is the code originally found under this C++ heading:

{{trans|Java}}

#include <sstream>

#include <stack>

return 0;

{{out}}

<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

=={{header|Ceylon}}==

ArrayList

assert(rpn == "3 4 2 * 1 5 - 2 3 ^ ^ / +");

print("\nthe result is ``rpn``");

{{out}}

<pre>input is 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

=={{header|Common Lisp}}==

Implemented as a state machine. The current state is the top of both the input queue and the operator stack. A signal function receives the current state and does a lookup to determine the signal to output. Based on the signal, the state (input queue and/or operator stack) is changed. The process iterates until both queue and stack are empty.

(defconstant operators "^*/+-")

(defconstant precedence '(-4 3 3 2 2))

(format t "~%INFIX:\"~A\"~%" expr)

(format t "RPN:\"~A\"~%" (rpn expr)))))

{{out}}

<pre>CL-USER(2): (main)

=={{header|D}}==

{{trans|Java}}

import std.stdio;

s.removeFront;

return v;

{{out}}

=={{header|EchoLisp}}==

(require 'hash)

(require 'tree)

(writeln 'infix infix)

(writeln 'RPN (queue->list Q)))

{{out}}

<pre>

=={{header|F_Sharp|F#}}==

type action = Shift | ReduceStack | ReduceInput

shunting_yard (State((Array.toList input), [], []))

|> (fun s -> s.report ReduceStack)

{{out}}

<pre> reduce [3] + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

===Source===

INTEGER KBD,MSG !I/O units.

13 FORMAT (L6," RPN: >",A,"<")

GO TO 10

===Results===

===A fuller symbol table===

The odd values for the precedences of the operators is driven by the model source being for a compiler able to handle much more complex arithmetic statements involving logical operations, variables, functions (some, like Max(a,b,c,...) with an arbitrary number of parameters), assignment within an expression, and conditionals such as <code>IF ''condition'' THEN ''exp1'' ELSE ''exp2'' OWISE ''exp3'' FI</code> - a three-value logic is employed. Similarly, ? stands for a "not a number" and ! for "Infinity". The fuller symbol table is...

Cunning ploys with precedence allow parameter evaluation, and right-to-left order as in x**y**z.

INTEGER OPSYMBOLS !Recognised operator symbols.

3 SYMB("^ ",14,2,"raise to power: also recognised is **."), !Uses the previous precedence level also!

4 SYMB("**",14,2,"raise to power: also recognised is ^."),

The USAGE field is for when there is a request for help, and the response uses the scanner's actual symbol table entries to formulate its assistance, rather than roll forth a separately-prepared wad of text.

=={{header|Go}}==

No error checking. No extra credit output, but there are some comments in the code.

import (

}

return

Output:

<pre>

Simple with zero error handling; some extra credit.

prec :: String -> Int

z

)

Output:

A more complete version with typed input, output and stack; StateT + Control.Lens for stateful actions; Either for both invalid tokens on parsing and unmatched parens when converting; readLine support.

import Control.Applicative

import Control.Lens

Left msg -> putStrLn msg >> main

Right ts -> putStrLn (showOutput (toRPN ts)) >> main

<pre>Enter expression: 3 + ( ( 4 + 5 )

=={{header|Icon}} and {{header|Unicon}}==

infix := "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"

printf("Infix = %i\n",infix)

every (s := "[ ") ||:= !L || " "

return s || "]"

{{libheader|Icon Programming Library}}

=={{header|J}}==

Code

NB. j does not have a verb based precedence.

NB. j evaluates verb noun sequences from right to left.

fulfill_requirement=: ;@:(' '&,&.>)@:algebra_to_rpn

Demonstration

fulfill_requirement '3+4*2/(1-5)^2^3'

3 4 2 * 1 5 - 2 3 ^ ^ / +

OUTPUT queue ^ ^ / +

3 4 2 * 1 5 - 2 3 ^ ^ / +

=={{header|Java}}==

{{works with|Java|7}}

public class ShuntingYard {

return sb.toString();

}

Output:

=={{header|JavaScript}}==

this.dataStore = [];

this.top = 0;

}

postfix += s.dataStore.reverse().join(" ");

Output:

=={{header|Julia}}==

Translation from the Wikipedia reference article's pseudocode.

function parseinfix2rpn(s)

outputq = []

teststring = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"

println("\nResult: $teststring becomes $(join(parseinfix2rpn(teststring), ' '))")

{{output}}

<pre>

=={{header|Kotlin}}==

{{trans|Java}}

import java.util.Stack

println("Postfix : ${infixToPostfix(e)}\n")

}

{{out}}

=={{header|Liberty BASIC}}==

global stack$,queue$

stack$=""

wend

end function

{{out}}

=={{header|Lua}}==

-- Lua 5.3.5

-- Retrieved from: https://devforum.roblox.com/t/more-efficient-way-to-implement-shunting-yard/1328711

print('infix:', goodmath)

print('postfix:', shuntingYard(goodmath))

{{out}}

=={{header|Mathematica}}/{{header|Wolfram Language}}==

StringRiffle[

ToString /@

While[stack != {}, AppendTo[out, stack[[-1]]];

stack = stack[[;; -2]]]; out]];

{{out}}

<pre>3 4 2 * 1 5 - / 2 3 ^ ^ +</pre>

=={{header|Nim}}==

type operator = tuple[prec:int, rassoc:bool]

echo &"for infix expression: '{input}' \n", "\nTOKEN OP STACK RPN OUTPUT"

{{out}}

=={{header|OCaml}}==

{{works with|ocaml|4.04}}

type associativity = Left | Right;;

let postfix = shunting_yard tkns in

print_endline (intercalate " " postfix);;

=={{header|Perl}}==

{{trans|Raku}}

'^' => 4,

'*' => 3,

local $, = " ";

print shunting_yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';

{{out}}

<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

=={{header|Phix}}==

{{Trans|Go}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #004080;">bool</span> <span style="color: #000000;">show_workings</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>

<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"4 * 2 + 1 - 5"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 2 * 1 + 5 -"</span><span style="color: #0000FF;">)</span>

<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"4 * 2 / (1 - 5) ^ 2"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 2 * 1 5 - 2 ^ /"</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

=={{header|PicoLisp}}==

Note: "^" is a meta-character and must be escaped in strings

(member Op '("\^" "*" "/" "+" "-")) )

(quit "Unbalanced Stack") )

(link (pop 'Stack))

Output:

Token Output Stack

3 3

3 4 2 * 1 5 - 2 3 ^ ^ / +

3 4 2 * 1 5 - 2 3 ^ ^ / +

=={{header|PL/I}}==

cvt: procedure options (main); /* 15 January 2012. */

declare (in, stack, out) character (100) varying;

end cvt;

Output:

INPUT STACK OUTPUT

3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) (

3 4 2 * 1 5 - 2 3 ^ ^ / +

3 4 2 * 1 5 - 2 3 ^ ^ / +

=={{header|Python}}==

Parenthesis are added to the operator table then special-cased in the code.

This solution includes the extra credit.

from pprint import pprint as pp

print( ' '.join('{cell:<{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row)))

;Sample output:

=={{header|Racket}}==

#lang racket

;print column of width w

((if (lasso? x) <= <) (prec x) (prec y)))))])

(shunt (append (reverse l) out) (cons x r) in (format "out ~a, push ~a" l x)))])])))

{{out}}

<pre>

=={{header|Raku}}==

(formerly Perl 6)

my %prec =

'^' => 4,

say shunting-yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';

{{out}}

<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

These REXX versions below allow multi-character tokens &nbsp; (both operands and operators).

===assume expression is correct===

parse arg x /*obtain optional argument from the CL.*/

if x='' then x= '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' /*Not specified? Then use the default.*/

/*──────────────────────────────────────────────────────────────────────────────────────────*/

isOp: return pos(arg(1),rOp) \== 0 /*is the first argument a "real" operator? */

'''output''' &nbsp; when using the default input:

<pre>

The &nbsp; '''select''' &nbsp; group could've been modified to check for mismatched parenthesis, but it would be harder to peruse the source.

parse arg x /*obtain optional argument from the CL.*/

if x='' then x= '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3' /*Not specified? Then use the default.*/

/*──────────────────────────────────────────────────────────────────────────────────────────*/

isOp: return pos(arg(1), Rop) \== 0 /*is the first argument a "real" operator? */

'''output''' &nbsp; when using the input: <tt> ) &nbsp; ( </tt>

<pre>

See [[Parsing/RPN/Ruby]]

outputs

<pre>for Infix expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

=={{header|Rust}}==

#[derive(Debug, Copy, Clone, PartialEq)]

calculate(postfix_tokens)

=={{header|Sidef}}==

{{trans|Raku}}

'^' => 4,

'*' => 3,

}

 

{{out}}

<pre>

=={{header|Standard ML}}==

datatype associativity = LEFT | RIGHT

type operator = { symbol : char, assoc : associativity, precedence : int }

parse' tokens [] []

end

=={{header|Swift}}==

// Using arrays for both stack and queue

print("input: \(input)")

print("output: \(output)")

{{out}}

<pre>

=={{header|Tcl}}==

# Helpers

}

Output:

<pre>

=={{header|UNIX Shell}}==

getopprec() {

}

===Output===

Output: 3

Operators:

End parsing

Output: 3 4 2 1 5 - 2 3 ^ ^ / * +

=={{header|VBA}}==

{{trans|Liberty BASIC}}

Option Base 1

Function Peek(stack)

Peek = stack(UBound(stack))

{{out}}

=={{header|Visual Basic .NET}}==

{{trans|C#}}

Class SymbolType

Public ReadOnly symbol As String

End Sub

{{out}}

<pre>3: stack[ ] out[ 3 ]

{{libheader|Wren-seq}}

{{libheader|Wren-pattern}}

import "/pattern" for Pattern

System.print("Infix : %(e)")

System.print("Postfix : %(infixToPostfix.call(e))\n")

{{out}}

{{trans|VBA}}

Function ShuntingYard(strInfix As String) As String

=={{header|zkl}}==

{{trans|Go}}

var opa=Dictionary("^",T(4,True), "*",T(3,False), // op:(prec,rAssoc)

"Queue|".println(rpn);

println();

{{out}}

<pre style="height:20ex;overflow:scroll;">