Parsing/Shunting-yard algorithm: Difference between revisions
Add Scala implementation
m (→{{header|Sidef}}: updated code) |
(Add Scala implementation) |
||
(45 intermediate revisions by 26 users not shown) | |||
Line 39:
* [[Parsing/RPN to infix conversion]].
<br><br>
=={{header|11l}}==
{{trans|Java}}
<syntaxhighlight lang="11l">F infix_to_postfix(infix)
-V ops = ‘-+/*^’
V sb = ‘’
[Int] s
L(token) infix.split(re:‘\s’)
I token.empty
L.continue
V c = token[0]
V? idx = ops.find(c)
I idx != N
I s.empty
s.append(idx)
E
L !s.empty
V prec2 = s.last I/ 2
V prec1 = idx I/ 2
I prec2 > prec1 | (prec2 == prec1 & c != ‘^’)
sb ‘’= ops[s.pop()]‘ ’
E
L.break
s.append(idx)
E I c == ‘(’
s.append(-2)
E I c == ‘)’
L s.last != -2
sb ‘’= ops[s.pop()]‘ ’
s.pop()
E
sb ‘’= token‘ ’
L !s.empty
sb ‘’= ops[s.pop()]‘ ’
R sb
V infix = ‘3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3’
print(‘infix: ’infix)
print(‘postfix: ’infix_to_postfix(infix))</syntaxhighlight>
{{out}}
<pre>
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
</pre>
=={{header|8th}}==
<syntaxhighlight lang="forth">\ Convert infix expression to postfix, using 'shunting-yard' algorithm
\ https://en.wikipedia.org/wiki/Shunting-yard_algorithm
\ precedence of infix tokens. negative means 'right-associative', otherwise left:
with: n
{
"+" : 2,
"-" : 2,
"/" : 3,
"*" : 3,
"^" : -4,
"(" : 1,
")" : -1
} var, tokens
: precedence \ s -- s n
tokens @ over m:@ nip
null? if drop 0 then ;
var ops
var out
: >out \ x --
out @ swap
a:push drop ;
: >ops \ op prec --
2 a:close
ops @ swap
a:push drop ;
: a:peek -1 a:@ ;
\ Check the array for items with greater or equal precedence,
\ and move them to the out queue:
: pop-ops \ op prec ops -- op prec ops
\ empty array, do nothing:
a:len not if ;; then
\ Look at top of ops stack:
a:peek a:open \ op p ops[] op2 p2
\ if the 'p2' is not less p (meaning item on top of stack is greater or equal
\ in precedence), then pop the item from the ops stack and push onto the out:
3 pick \ p2 p
< not if
\ op p ops[] op2
>out a:pop drop recurse ;;
then
drop ;
: right-paren
"RIGHTPAREN" . cr
2drop
\ move non-left-paren from ops and move to out:
ops @
repeat
a:len not if
break
else
a:pop a:open
1 = if
2drop ;;
else
>out
then
then
again drop ;
: .state \ n --
drop \ "Token: %s\n" s:strfmt .
"Out: " .
out @ ( . space drop ) a:each drop cr
"ops: " . ops @ ( 0 a:@ . space 2drop ) a:each drop cr cr ;
: handle-number \ s n --
"NUMBER " . over . cr
drop >out ;
: left-paren \ s n --
"LEFTPAREN" . cr
>ops ;
: handle-op \ s n --
"OPERATOR " . over . cr
\ op precedence
\ Is the current op left-associative?
dup sgn 1 = if
\ it is, so check the ops array for items with greater or equal precedence,
\ and move them to the out queue:
ops @ pop-ops drop
then
\ push the operator
>ops ;
: handle-token \ s --
precedence dup not if
\ it's a number:
handle-number
else
dup 1 = if left-paren
else dup -1 = if right-paren
else handle-op
then then
then ;
: infix>postfix \ s -- s
/\s+/ s:/ \ split to indiviual whitespace-delimited tokens
\ Initialize our data structures
a:new ops ! a:new out !
(
nip dup >r
handle-token
r> .state
) a:each drop
\ remove all remaining ops and put on output:
out @
ops @ a:rev
( nip a:open drop a:push ) a:each drop
\ final string:
" " a:join ;
"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" infix>postfix . cr
"Expected: \n" . "3 4 2 * 1 5 - 2 3 ^ ^ / +" . cr
bye
</syntaxhighlight>
{{out}}
<pre>NUMBER 3
Out: 3
ops:
OPERATOR +
Out: 3
ops: +
NUMBER 4
Out: 3 4
ops: +
OPERATOR *
Out: 3 4
ops: + *
NUMBER 2
Out: 3 4 2
ops: + *
OPERATOR /
Out: 3 4 2 *
ops: + /
LEFTPAREN
Out: 3 4 2 *
ops: + / (
NUMBER 1
Out: 3 4 2 * 1
ops: + / (
OPERATOR -
Out: 3 4 2 * 1
ops: + / ( -
NUMBER 5
Out: 3 4 2 * 1 5
ops: + / ( -
RIGHTPAREN
Out: 3 4 2 * 1 5 -
ops: + /
OPERATOR ^
Out: 3 4 2 * 1 5 -
ops: + / ^
NUMBER 2
Out: 3 4 2 * 1 5 - 2
ops: + / ^
OPERATOR ^
Out: 3 4 2 * 1 5 - 2
ops: + / ^ ^
NUMBER 3
Out: 3 4 2 * 1 5 - 2 3
ops: + / ^ ^
3 4 2 * 1 5 - 2 3 ^ ^ / +
Expected:
3 4 2 * 1 5 - 2 3 ^ ^ / +
</pre>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
<syntaxhighlight lang="algol68">BEGIN
# 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 #
PROC parse = ( STRING s )STRING:
BEGIN
# add to the output #
PROC output element = ( CHAR c )VOID:
BEGIN
output[ output pos +:= 1 ] := c;
output pos +:= 1
END # output element # ;
PROC stack op = ( CHAR c )VOID: stack[ stack pos +:= 1 ] := c;
# unstacks and returns the top operator on the stack - stops the program if the stack is empty #
PROC unstack = CHAR:
IF stack pos < 1 THEN
# empty stack #
print( ( "Stack underflow", newline ) );
stop
ELSE
# still something on the stack to unstack #
CHAR result = stack[ stack pos ];
stack[ stack pos ] := " ";
stack pos -:= 1;
result
FI # unstack # ;
# returns the priority of the operator o - which must be one of "(", "^", "*", "/", "+" or "-" #
PROC priority of = ( CHAR o )INT: IF o = "(" THEN -1 ELIF o = "^" THEN 4 ELIF o = "*" OR o = "/" THEN 3 ELSE 2 FI;
# returns TRUE if o is a right-associative operator, FALSE otherwise #
PROC right = ( CHAR c )BOOL: c = "^";
PROC lower or equal priority = ( CHAR c )BOOL:
IF stack pos < 1 THEN FALSE # empty stack #
ELSE priority of( c ) <= priority of( stack[ stack pos ] )
FI # lower or equal priority # ;
PROC lower priority = ( CHAR c )BOOL:
IF stack pos < 1 THEN FALSE # empty stack #
ELSE priority of( c ) < priority of( stack[ stack pos ] )
FI # lower priority # ;
# max stack size and output size #
INT max stack = 32;
# stack and output queue #
[ 1 : max stack ]CHAR stack;
[ 1 : max stack ]CHAR output;
FOR c pos TO max stack DO stack[ c pos ] := output[ c pos ] := " " OD;
# stack pointer and output queue pointer #
INT stack pos := 0;
INT output pos := 0;
print( ( "Parsing: ", s, newline ) );
print( ( "token output stack", newline ) );
FOR s pos FROM LWB s TO UPB s DO
CHAR c = s[ s pos ];
IF c /= " " THEN
IF c >= "0" AND c <= "9" THEN output element( c )
ELIF c = "(" THEN stack op( c )
ELIF c = ")" THEN
# close bracket - unstack to the matching "(" and unstack the "(" #
WHILE CHAR op char = unstack;
op char /= "("
DO
output element( op char )
OD
ELIF right( c ) THEN
# right associative operator #
WHILE lower priority( c ) DO output element( unstack ) OD;
stack op( c )
ELSE
# must be left associative #
WHILE lower or equal priority( c ) DO output element( unstack ) OD;
stack op( c )
FI;
print( ( c, " ", output, " ", stack, newline ) )
FI
OD;
WHILE stack pos >= 1 DO output element( unstack ) OD;
output[ 1 : output pos ]
END # parse # ;
print( ( "result: ", parse( "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" ), newline ) )
END</syntaxhighlight>
{{out}}
<pre>
Parsing: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
token output stack
3 3
+ 3 +
4 3 4 +
* 3 4 +*
2 3 4 2 +*
/ 3 4 2 * +/
( 3 4 2 * +/(
1 3 4 2 * 1 +/(
- 3 4 2 * 1 +/(-
5 3 4 2 * 1 5 +/(-
) 3 4 2 * 1 5 - +/
^ 3 4 2 * 1 5 - +/^
2 3 4 2 * 1 5 - 2 +/^
^ 3 4 2 * 1 5 - 2 +/^^
3 3 4 2 * 1 5 - 2 3 +/^^
result: 3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<
#NoEnv
Line 111 ⟶ 463:
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'
Line 141 ⟶ 493:
=={{header|C}}==
Requires a functioning ANSI terminal and Enter key.
<
#include <regex.h>
#include <stdio.h>
Line 242 ⟶ 594:
str_tok_t *t, tok;
prec_booster = l_queue = l_stack = 0;
display(s);
while (*s) {
Line 294 ⟶ 646:
display(s);
}
if (p->prec > 0)
fail("unexpected eol", s);
return 1;
Line 308 ⟶ 663:
"a^(b + c/d * .1e5)!", /* unknown op */
"(1**2)**3", /* OK */
"2 + 2 *", /* unexpected eol */
0
};
Line 321 ⟶ 677:
return 0;
}</
;Output:
Line 457 ⟶ 813:
Testing string `123' <enter>
^C</pre>
=={{header|C sharp}}==
{{works with|C sharp|7.0}}
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static void Main() {
string infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
Console.WriteLine(infix.ToPostfix());
}
}
public static class ShuntingYard
{
private static readonly Dictionary<string, (string symbol, int precedence, bool rightAssociative)> operators
= new (string symbol, int precedence, bool rightAssociative) [] {
("^", 4, true),
("*", 3, false),
("/", 3, false),
("+", 2, false),
("-", 2, false)
}.ToDictionary(op => op.symbol);
public static string ToPostfix(this string infix) {
string[] tokens = infix.Split(' ');
var stack = new Stack<string>();
var output = new List<string>();
foreach (string token in tokens) {
if (int.TryParse(token, out _)) {
output.Add(token);
Print(token);
} else if (operators.TryGetValue(token, out var op1)) {
while (stack.Count > 0 && operators.TryGetValue(stack.Peek(), out var op2)) {
int c = op1.precedence.CompareTo(op2.precedence);
if (c < 0 || !op1.rightAssociative && c <= 0) {
output.Add(stack.Pop());
} else {
break;
}
}
stack.Push(token);
Print(token);
} else if (token == "(") {
stack.Push(token);
Print(token);
} else if (token == ")") {
string top = "";
while (stack.Count > 0 && (top = stack.Pop()) != "(") {
output.Add(top);
}
if (top != "(") throw new ArgumentException("No matching left parenthesis.");
Print(token);
}
}
while (stack.Count > 0) {
var top = stack.Pop();
if (!operators.ContainsKey(top)) throw new ArgumentException("No matching right parenthesis.");
output.Add(top);
}
Print("pop");
return string.Join(" ", output);
//Yikes!
void Print(string action) => Console.WriteLine($"{action + ":",-4} {$"stack[ {string.Join(" ", stack.Reverse())} ]",-18} {$"out[ {string.Join(" ", output)} ]"}");
//A little more readable?
void Print(string action) => Console.WriteLine("{0,-4} {1,-18} {2}", action + ":", $"stack[ {string.Join(" ", stack.Reverse())} ]", $"out[ {string.Join(" ", output)} ]");
}
}</syntaxhighlight>
{{out}}
<pre>
3: stack[ ] out[ 3 ]
+: stack[ + ] out[ 3 ]
4: stack[ + ] out[ 3 4 ]
*: stack[ + * ] out[ 3 4 ]
2: stack[ + * ] out[ 3 4 2 ]
/: stack[ + / ] out[ 3 4 2 * ]
(: stack[ + / ( ] out[ 3 4 2 * ]
1: stack[ + / ( ] out[ 3 4 2 * 1 ]
-: stack[ + / ( - ] out[ 3 4 2 * 1 ]
5: stack[ + / ( - ] out[ 3 4 2 * 1 5 ]
): stack[ + / ] out[ 3 4 2 * 1 5 - ]
^: stack[ + / ^ ] out[ 3 4 2 * 1 5 - ]
2: stack[ + / ^ ] out[ 3 4 2 * 1 5 - 2 ]
^: stack[ + / ^ ^ ] out[ 3 4 2 * 1 5 - 2 ]
3: stack[ + / ^ ^ ] out[ 3 4 2 * 1 5 - 2 3 ]
pop: stack[ ] out[ 3 4 2 * 1 5 - 2 3 ^ ^ / + ]
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|C++}}==
== Note 1 ==
Shunting Yard is conceptually very simple, but it requires a whole lot of help to validate
an expression. The best way to handle this, IMO, is as a separate pass to check the tokens
for incorrect patterns and matching parentheses and transform things like unary minus into
a unique token identifier.
That said, this Rosetta Code Task specifically obviates validation, though, so we don't do
any of that below. In other words, binary operators only, and garbage in == garbage out.
== Note 2 ==
This example leverages some nice C++17 features, so turn them on when you compile.
cl /EHsc /W4 /Ox /std:c++17 /utf-8 a.cpp
clang++ -Wall -pedantic-errors -O3 -std=c++17 a.cpp
<syntaxhighlight lang="cpp">#include <ciso646>
#include <iostream>
#include <regex>
#include <sstream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using std::vector;
using std::string;
//-------------------------------------------------------------------------------------------------
// throw error( "You ", profanity, "ed up!" ); // Don't mess up, okay?
//-------------------------------------------------------------------------------------------------
#include <exception>
#include <stdexcept>
template <typename...Args> std::runtime_error error( Args...args )
{
return std::runtime_error( (std::ostringstream{} << ... << args).str() );
};
//-------------------------------------------------------------------------------------------------
// Stack
//-------------------------------------------------------------------------------------------------
// Let us co-opt a vector for our stack type.
// C++ pedants: no splicing possible == totally okay to do this.
//
// Note: C++ provides a more appropriate std::stack class, except that the task requires us to
// be able to display its contents, and that kind of access is an expressly non-stack behavior.
template <typename T> struct stack : public std::vector <T>
{
using base_type = std::vector <T> ;
T push ( const T& x ) { base_type::push_back( x ); return x; }
const T& top () { return base_type::back(); }
T pop () { T x = std::move( top() ); base_type::pop_back(); return x; }
bool empty() { return base_type::empty(); }
};
//-------------------------------------------------------------------------------------------------
using Number = double;
//-------------------------------------------------------------------------------------------------
// Numbers are already too awesome to need extra diddling.
//-------------------------------------------------------------------------------------------------
// Operators
//-------------------------------------------------------------------------------------------------
using Operator_Name = string;
using Precedence = int;
enum class Associates { none, left_to_right, right_to_left };
struct Operator_Info { Precedence precedence; Associates associativity; };
std::unordered_map <Operator_Name, Operator_Info> Operators =
{
{ "^", { 4, Associates::right_to_left } },
{ "*", { 3, Associates::left_to_right } },
{ "/", { 3, Associates::left_to_right } },
{ "+", { 2, Associates::left_to_right } },
{ "-", { 2, Associates::left_to_right } },
};
Precedence precedence ( const Operator_Name& op ) { return Operators[ op ].precedence; }
Associates associativity( const Operator_Name& op ) { return Operators[ op ].associativity; }
//-------------------------------------------------------------------------------------------------
using Token = string;
//-------------------------------------------------------------------------------------------------
bool is_number ( const Token& t ) { return regex_match( t, std::regex{ R"z((\d+(\.\d*)?|\.\d+)([Ee][\+\-]?\d+)?)z" } ); }
bool is_operator ( const Token& t ) { return Operators.count( t ); }
bool is_open_parenthesis ( const Token& t ) { return t == "("; }
bool is_close_parenthesis( const Token& t ) { return t == ")"; }
bool is_parenthesis ( const Token& t ) { return is_open_parenthesis( t ) or is_close_parenthesis( t ); }
//-------------------------------------------------------------------------------------------------
// std::cout << a_vector_of_something;
//-------------------------------------------------------------------------------------------------
// Weird C++ stream operator stuff (for I/O).
// Don't worry if this doesn't look like it makes any sense.
//
template <typename T> std::ostream& operator << ( std::ostream& outs, const std::vector <T> & xs )
{
std::size_t n = 0; for (auto x : xs) outs << (n++ ? " " : "") << x; return outs;
}
//-------------------------------------------------------------------------------------------------
// Progressive_Display
//-------------------------------------------------------------------------------------------------
// This implements the required task:
// "use the algorithm to show the changes in the operator
// stack and RPN output as each individual token is processed"
//
#include <iomanip>
struct Progressive_Display
{
string token_name;
string token_type;
Progressive_Display() // Header for the table we are going to generate
{
std::cout << "\n"
" INPUT │ TYPE │ ACTION │ STACK │ OUTPUT\n"
"────────┼──────┼──────────────────┼──────────────┼─────────────────────────────\n";
}
Progressive_Display& operator () ( const Token& token ) // Ready the first two columns
{
token_name = token;
token_type = is_operator ( token ) ? "op"
: is_parenthesis( token ) ? "()"
: is_number ( token ) ? "num"
: "";
return *this;
}
Progressive_Display& operator () ( // Display all columns of a row
const string & description,
const stack <Token> & stack,
const vector <Token> & output )
{
std::cout << std::right
<< std::setw( 7 ) << token_name << " │ " << std::left
<< std::setw( 4 ) << token_type << " │ "
<< std::setw( 16 ) << description << " │ "
<< std::setw( 12 ) << (std::ostringstream{} << stack).str() << " │ "
<< output << "\n";
return operator () ( "" ); // Reset the first two columns to empty for next iteration
}
};
//-------------------------------------------------------------------------------------------------
vector <Token> parse( const vector <Token> & tokens )
//-------------------------------------------------------------------------------------------------
{
vector <Token> output;
stack <Token> stack;
Progressive_Display display;
for (auto token : tokens) // Shunting Yard takes a single linear pass through the tokens
//.........................................................................
if (is_number( token ))
{
output.push_back( token );
display( token )( "num --> output", stack, output );
}
//.........................................................................
else if (is_operator( token ) or is_parenthesis( token ))
{
display( token );
if (!is_open_parenthesis( token ))
{
// pop --> output
// : until '(' if token is ')'
// : while prec(token) > prec(top)
// : while prec(token) == prec(top) AND assoc(token) is left-to-right
while (!stack.empty()
and ( (is_close_parenthesis( token ) and !is_open_parenthesis( stack.top() ))
or (precedence( stack.top() ) > precedence( token ))
or ( (precedence( stack.top() ) == precedence( token ))
and (associativity( token ) == Associates::left_to_right))))
{
output.push_back( stack.pop() );
display( "pop --> output", stack, output );
}
// If we popped until '(' because token is ')', toss both parens
if (is_close_parenthesis( token ))
{
stack.pop();
display( "pop", stack, output );
}
}
// Everything except ')' --> stack
if (!is_close_parenthesis( token ))
{
stack.push( token );
display( "push op", stack, output );
}
}
//.........................................................................
else throw error( "unexpected token: ", token );
// Anything left on the operator stack just gets moved to the output
display( "END" );
while (!stack.empty())
{
output.push_back( stack.pop() );
display( "pop --> output", stack, output );
}
return output;
}
//-------------------------------------------------------------------------------------------------
int main( int argc, char** argv )
//-------------------------------------------------------------------------------------------------
try
{
auto tokens = vector <Token> ( argv+1, argv+argc );
auto rpn_expr = parse( tokens );
std::cout
<< "\nInfix = " << tokens
<< "\nRPN = " << rpn_expr
<< "\n";
}
catch (std::exception e)
{
std::cerr << "error: " << e.what() << "\n";
return 1;
}</syntaxhighlight>
{{out}}
<pre>C:\Users\JRandom\cpp> a.exe 3 + 4 * 2 / ( 1 - 5 ) ^^ 2 ^^ 3
INPUT │ TYPE │ ACTION │ STACK │ OUTPUT
────────┼──────┼──────────────────┼──────────────┼─────────────────────────────
3 │ num │ num --> output │ │ 3
+ │ op │ push op │ + │ 3
4 │ num │ num --> output │ + │ 3 4
* │ op │ push op │ + * │ 3 4
2 │ num │ num --> output │ + * │ 3 4 2
/ │ op │ pop --> output │ + │ 3 4 2 *
│ │ push op │ + / │ 3 4 2 *
( │ () │ push op │ + / ( │ 3 4 2 *
1 │ num │ num --> output │ + / ( │ 3 4 2 * 1
- │ op │ push op │ + / ( - │ 3 4 2 * 1
5 │ num │ num --> output │ + / ( - │ 3 4 2 * 1 5
) │ () │ pop --> output │ + / ( │ 3 4 2 * 1 5 -
│ │ pop │ + / │ 3 4 2 * 1 5 -
^ │ op │ push op │ + / ^ │ 3 4 2 * 1 5 -
2 │ num │ num --> output │ + / ^ │ 3 4 2 * 1 5 - 2
^ │ op │ push op │ + / ^ ^ │ 3 4 2 * 1 5 - 2
3 │ num │ num --> output │ + / ^ ^ │ 3 4 2 * 1 5 - 2 3
END │ │ pop --> output │ + / ^ │ 3 4 2 * 1 5 - 2 3 ^
│ │ pop --> output │ + / │ 3 4 2 * 1 5 - 2 3 ^ ^
│ │ pop --> output │ + │ 3 4 2 * 1 5 - 2 3 ^ ^ /
│ │ pop --> output │ │ 3 4 2 * 1 5 - 2 3 ^ ^ / +
Infix = 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
RPN = 3 4 2 * 1 5 - 2 3 ^ ^ / +
C:\Users\JRandom\cpp> _
</pre>
(Remember that on Windows you must double the caret symbol at the prompt.)
Here is the code originally found under this C++ heading:
{{trans|Java}}
<syntaxhighlight lang="cpp">#include <iostream>
#include <sstream>
#include <stack>
std::string infixToPostfix(const std::string& infix) {
const std::string ops = "-+/*^";
std::stringstream ss;
std::stack<int> s;
std::stringstream input(infix);
std::string token;
while (std::getline(input, token, ' ')) {
if (token.empty()) {
continue;
}
char c = token[0];
size_t idx = ops.find(c);
// check for operator
if (idx != std::string::npos) {
while (!s.empty()) {
int prec2 = s.top() / 2;
int prec1 = idx / 2;
if (prec2 > prec1 || (prec2 == prec1 && c != '^')) {
ss << ops[s.top()] << ' ';
s.pop();
} else break;
}
s.push(idx);
} else if (c == '(') {
s.push(-2); // -2 stands for '('
} else if (c == ')') {
// until '(' on stack, pop operators.
while (s.top() != -2) {
ss << ops[s.top()] << ' ';
s.pop();
}
s.pop();
} else {
ss << token << ' ';
}
}
while (!s.empty()) {
ss << ops[s.top()] << ' ';
s.pop();
}
return ss.str();
}
int main() {
std::string infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
std::cout << "infix: " << infix << '\n';
std::cout << "postfix: " << infixToPostfix(infix) << '\n';
return 0;
}</syntaxhighlight>
{{out}}
<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|Ceylon}}==
<
ArrayList
Line 564 ⟶ 1,345:
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
Line 592 ⟶ 1,373:
the result is 3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{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))
Line 683 ⟶ 1,465:
(format t "~%INFIX:\"~A\"~%" expr)
(format t "RPN:\"~A\"~%" (rpn expr)))))
</syntaxhighlight>
{{out}}
<pre>CL-USER(2): (main)
Line 713 ⟶ 1,495:
RPN:"3 4 2 * 1 5 - 2 3 ^ ^ / +"
NIL</pre>
=={{header|D}}==
{{trans|Java}}
<syntaxhighlight lang="d">import std.container;
import std.stdio;
void main() {
string infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
writeln("infix: ", infix);
writeln("postfix: ", infixToPostfix(infix));
}
string infixToPostfix(string infix) {
import std.array;
/* To find out the precedence, we take the index of the
token in the ops string and divide by 2 (rounding down).
This will give us: 0, 0, 1, 1, 2 */
immutable ops = ["+", "-", "/", "*", "^"];
auto sb = appender!string;
SList!int stack;
// split the input on whitespace
foreach (token; infix.split) {
if (token.empty) {
continue;
}
int idx = ops.indexOf(token);
// check for operator
if (idx != -1) {
while (!stack.empty) {
int prec2 = stack.peek / 2;
int prec1 = idx / 2;
if (prec2 > prec1 || (prec2 == prec1 && token != "^")) {
sb.put(ops[stack.pop]);
sb.put(' ');
} else {
break;
}
}
stack.push(idx);
} else if (token == "(") {
stack.push(-2); // -2 stands for '('
} else if (token == ")") {
// until '(' on stack, pop operators.
while (stack.peek != -2) {
sb.put(ops[stack.pop]);
sb.put(' ');
}
stack.pop();
} else {
sb.put(token);
sb.put(' ');
}
}
while (!stack.empty) {
sb.put(ops[stack.pop]);
sb.put(' ');
}
return sb.data;
}
// Find the first index of the specified value, or -1 if not found.
int indexOf(T)(const T[] a, const T v) {
foreach(i,e; a) {
if (e == v) {
return i;
}
}
return -1;
}
// Convienience for adding a new element
void push(T)(ref SList!T s, T v) {
s.insertFront(v);
}
// Convienience for accessing the top element
auto peek(T)(SList!T s) {
return s.front;
}
// Convienience for removing and returning the top element
auto pop(T)(ref SList!T s) {
auto v = s.front;
s.removeFront;
return v;
}</syntaxhighlight>
{{out}}
<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|EchoLisp}}==
<
(require 'hash)
(require 'tree)
Line 768 ⟶ 1,647:
(writeln 'infix infix)
(writeln 'RPN (queue->list Q)))
</syntaxhighlight>
{{out}}
<pre>
Line 794 ⟶ 1,673:
=={{header|F_Sharp|F#}}==
<
type action = Shift | ReduceStack | ReduceInput
Line 888 ⟶ 1,767:
shunting_yard (State((Array.toList input), [], []))
|> (fun s -> s.report ReduceStack)
0</
{{out}}
<pre> reduce [3] + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 929 ⟶ 1,808:
===Source===
<
INTEGER KBD,MSG !I/O units.
Line 1,162 ⟶ 2,041:
13 FORMAT (L6," RPN: >",A,"<")
GO TO 10
END</
===Results===
Line 1,222 ⟶ 2,101:
===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.
Line 1,269 ⟶ 2,148:
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 ^."),
5 SYMB("! ",15,1,"factorial, sortof, just for fun.")/))</
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 (
Line 1,345 ⟶ 2,224:
}
return
}</
Output:
<pre>
Line 1,356 ⟶ 2,235:
Simple with zero error handling; some extra credit.
<
prec :: String -> Int
prec "^" = 4
prec "*" = 3
Line 1,364 ⟶ 2,244:
prec "-" = 2
leftAssoc :: String -> Bool
leftAssoc "^" = False
leftAssoc _ = True
isOp
isOp
isOp _ = False
simSYA
simSYA xs
where
final =
lastStep =
)
$ last final
( reverse (takeWhile testOp st) <> out,
(t :) (dropWhile testOp st),
t
)
| t == "(" = (out, "(" : st, t)
| t == ")" =
( reverse (takeWhile (/= "(") st) <> out,
tail $ dropWhile (/= "(") st,
t
)
| otherwise = (t : out, st, t)
where
testOp x =
isOp x
&& ( leftAssoc t && prec t == prec x
|| prec t < prec x
)
main :: IO ()
main = do
mapM_
( \(x, y, z) ->
printf
"%30s%20s%7s\n"
(unwords $ reverse x)
(unwords y)
z
)
$ simSYA $ words a</syntaxhighlight>
Output:
Line 1,413 ⟶ 2,319:
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
Line 1,509 ⟶ 2,415:
Left msg -> putStrLn msg >> main
Right ts -> putStrLn (showOutput (toRPN ts)) >> main
</syntaxhighlight>
<pre>Enter expression: 3 + ( ( 4 + 5 )
Line 1,524 ⟶ 2,430:
=={{header|Icon}} and {{header|Unicon}}==
<
infix := "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
printf("Infix = %i\n",infix)
Line 1,587 ⟶ 2,493:
every (s := "[ ") ||:= !L || " "
return s || "]"
end</
{{libheader|Icon Programming Library}}
Line 1,617 ⟶ 2,523:
=={{header|J}}==
Code
<syntaxhighlight lang="j">
NB. j does not have a verb based precedence.
NB. j evaluates verb noun sequences from right to left.
Line 1,762 ⟶ 2,668:
fulfill_requirement=: ;@:(' '&,&.>)@:algebra_to_rpn
</syntaxhighlight>
Demonstration
<syntaxhighlight lang="j">
fulfill_requirement '3+4*2/(1-5)^2^3'
3 4 2 * 1 5 - 2 3 ^ ^ / +
Line 1,820 ⟶ 2,726:
OUTPUT queue ^ ^ / +
3 4 2 * 1 5 - 2 3 ^ ^ / +
</syntaxhighlight>
=={{header|Java}}==
{{works with|Java|7}}
<
public class ShuntingYard {
Line 1,835 ⟶ 2,741:
static String infixToPostfix(String infix) {
/* To find out the precedence, we take the index of the
token in the ops string and divide by 2 (rounding down).
This will give us: 0, 0, 1, 1, 2 */
final String ops = "-+/*^";
StringBuilder sb = new StringBuilder();
Stack<Integer> s = new Stack<>();
Line 1,878 ⟶ 2,788:
return sb.toString();
}
}</
Output:
Line 1,886 ⟶ 2,796:
=={{header|JavaScript}}==
<
this.dataStore = [];
this.top = 0;
Line 1,953 ⟶ 2,863:
}
}
postfix += s.dataStore.reverse().join(" ");
print(postfix);</syntaxhighlight>
Output:
Line 1,962 ⟶ 2,870:
<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / + </pre>
=={{header|Julia}}==
Translation from the Wikipedia reference article's pseudocode.
<syntaxhighlight lang="julia">
function parseinfix2rpn(s)
outputq = []
opstack = []
infix = split(s)
for tok in infix
if all(isnumber, tok)
push!(outputq, tok)
elseif tok == "("
push!(opstack, tok)
elseif tok == ")"
while !isempty(opstack) && (op = pop!(opstack)) != "("
push!(outputq, op)
end
else # operator
while !isempty(opstack)
op = pop!(opstack)
if Base.operator_precedence(Symbol(op)) > Base.operator_precedence(Symbol(tok)) ||
(Base.operator_precedence(Symbol(op)) ==
Base.operator_precedence(Symbol(tok)) && op != "^")
push!(outputq, op)
else
push!(opstack, op) # undo peek
break
end
end
push!(opstack, tok)
end
println("The working output stack is $outputq")
end
while !isempty(opstack)
if (op = pop!(opstack)) == "("
throw("mismatched parentheses")
else
push!(outputq, op)
end
end
outputq
end
teststring = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
println("\nResult: $teststring becomes $(join(parseinfix2rpn(teststring), ' '))")
</syntaxhighlight>
{{output}}
<pre>
The working output stack is Any["3"]
The working output stack is Any["3"]
The working output stack is Any["3", "4"]
The working output stack is Any["3", "4"]
The working output stack is Any["3", "4", "2"]
The working output stack is Any["3", "4", "2", "*"]
The working output stack is Any["3", "4", "2", "*"]
The working output stack is Any["3", "4", "2", "*", "1"]
The working output stack is Any["3", "4", "2", "*", "1"]
The working output stack is Any["3", "4", "2", "*", "1", "5"]
The working output stack is Any["3", "4", "2", "*", "1", "5", "-"]
The working output stack is Any["3", "4", "2", "*", "1", "5", "-"]
The working output stack is Any["3", "4", "2", "*", "1", "5", "-", "2"]
The working output stack is Any["3", "4", "2", "*", "1", "5", "-", "2"]
The working output stack is Any["3", "4", "2", "*", "1", "5", "-", "2", "3"]
Result: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 becomes 3 4 2 * 1 5 - 2 3 ^ ^ / +
</pre>
=={{header|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="scala">// version 1.2.0
import java.util.Stack
/* To find out the precedence, we take the index of the
token in the OPS string and divide by 2 (rounding down).
This will give us: 0, 0, 1, 1, 2 */
const val OPS = "-+/*^"
fun infixToPostfix(infix: String): String {
val sb = StringBuilder()
val s = Stack<Int>()
val rx = Regex("""\s""")
for (token in infix.split(rx)) {
if (token.isEmpty()) continue
val c = token[0]
val idx = OPS.indexOf(c)
// check for operator
if (idx != - 1) {
if (s.isEmpty()) {
s.push(idx)
}
else {
while (!s.isEmpty()) {
val prec2 = s.peek() / 2
val prec1 = idx / 2
if (prec2 > prec1 || (prec2 == prec1 && c != '^')) {
sb.append(OPS[s.pop()]).append(' ')
}
else break
}
s.push(idx)
}
}
else if (c == '(') {
s.push(-2) // -2 stands for '('
}
else if (c == ')') {
// until '(' on stack, pop operators.
while (s.peek() != -2) sb.append(OPS[s.pop()]).append(' ')
s.pop()
}
else {
sb.append(token).append(' ')
}
}
while (!s.isEmpty()) sb.append(OPS[s.pop()]).append(' ')
return sb.toString()
}
fun main(args: Array<String>) {
val es = listOf(
"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3",
"( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )"
)
for (e in es) {
println("Infix : $e")
println("Postfix : ${infixToPostfix(e)}\n")
}
}</syntaxhighlight>
{{out}}
<pre>
Infix : 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Postfix : 3 4 2 * 1 5 - 2 3 ^ ^ / +
Infix : ( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )
Postfix : 1 2 + 3 4 + ^ 5 6 + ^
</pre>
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
global stack$,queue$
stack$=""
Line 2,080 ⟶ 3,127:
wend
end function
</syntaxhighlight>
{{out}}
Line 2,106 ⟶ 3,153:
</pre>
=={{header|
<syntaxhighlight lang="lua">
-- Lua 5.3.5
-- Retrieved from: https://devforum.roblox.com/t/more-efficient-way-to-implement-shunting-yard/1328711
-- Modified slightly to ensure conformity with other code snippets posted here
local OPERATOR_PRECEDENCE = {
-- [operator] = { [precedence], [is left assoc.] }
['-'] = { 2, true };
['+'] = { 2, true };
['/'] = { 3, true };
['*'] = { 3, true };
['^'] = { 4, false };
}
local function shuntingYard(expression)
local outputQueue = { }
local operatorStack = { }
local number, operator, parenthesis, fcall
while #expression > 0 do
local nStartPos, nEndPos = string.find(expression, '(%-?%d+%.?%d*)')
if nStartPos == 1 and nEndPos > 0 then
number, expression = string.sub(expression, nStartPos, nEndPos), string.sub(expression, nEndPos + 1)
table.insert(outputQueue, tonumber(number))
print('token:', number)
print('queue:', unpack(outputQueue))
print('stack:', unpack(operatorStack))
else
local oStartPos, oEndPos = string.find(expression, '([%-%+%*/%^])')
if oStartPos == 1 and oEndPos > 0 then
operator, expression = string.sub(expression, oStartPos, oEndPos), string.sub(expression, oEndPos + 1)
if #operatorStack > 0 then
while operatorStack[1] ~= '(' do
local operator1Precedence = OPERATOR_PRECEDENCE[operator]
local operator2Precedence = OPERATOR_PRECEDENCE[operatorStack[1]]
if operator2Precedence and ((operator2Precedence[1] > operator1Precedence[1]) or (operator2Precedence[1] == operator1Precedence[1] and operator1Precedence[2])) then
table.insert(outputQueue, table.remove(operatorStack, 1))
else
break
end
end
end
table.insert(operatorStack, 1, operator)
print('token:', operator)
print('queue:', unpack(outputQueue))
print('stack:', unpack(operatorStack))
else
local pStartPos, pEndPos = string.find(expression, '[%(%)]')
if pStartPos == 1 and pEndPos > 0 then
parenthesis, expression = string.sub(expression, pStartPos, pEndPos), string.sub(expression, pEndPos + 1)
if parenthesis == ')' then
while operatorStack[1] ~= '(' do
assert(#operatorStack > 0)
table.insert(outputQueue, table.remove(operatorStack, 1))
end
assert(operatorStack[1] == '(')
table.remove(operatorStack, 1)
else
table.insert(operatorStack, 1, parenthesis)
end
print('token:', parenthesis)
print('queue:', unpack(outputQueue))
print('stack:', unpack(operatorStack))
else
local wStartPos, wEndPos = string.find(expression, '%s+')
if wStartPos == 1 and wEndPos > 0 then
expression = string.sub(expression, wEndPos + 1)
else
error('Invalid character set: '.. expression)
end
end
end
end
end
while #operatorStack > 0 do
assert(operatorStack[1] ~= '(')
table.insert(outputQueue, table.remove(operatorStack, 1))
end
return table.concat(outputQueue, ' ')
end
local goodmath = '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
print('infix:', goodmath)
print('postfix:', shuntingYard(goodmath))
</syntaxhighlight>
{{out}}
<pre>
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
token: 3
queue: 3
stack:
token: +
queue: 3
stack: +
token: 4
queue: 3 4
stack: +
token: *
queue: 3 4
stack: * +
token: 2
queue: 3 4 2
stack: * +
token: /
queue: 3 4 2 *
stack: / +
token: (
queue: 3 4 2 *
stack: ( / +
token: 1
queue: 3 4 2 * 1
stack: ( / +
token: -
queue: 3 4 2 * 1
stack: - ( / +
token: 5
queue: 3 4 2 * 1 5
stack: - ( / +
token: )
queue: 3 4 2 * 1 5 -
stack: / +
token: ^
queue: 3 4 2 * 1 5 -
stack: ^ / +
token: 2
queue: 3 4 2 * 1 5 - 2
stack: ^ / +
token: ^
queue: 3 4 2 * 1 5 - 2
stack: ^ ^ / +
token: 3
queue: 3 4 2 * 1 5 - 2 3
stack: ^ ^ / +
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">rpn[str_] :=
StringRiffle[
ToString /@
Line 2,138 ⟶ 3,339:
While[stack != {}, AppendTo[out, stack[[-1]]];
stack = stack[[;; -2]]]; out]];
Print[rpn["3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]];</
{{out}}
<pre>3 4 2 * 1 5 - / 2 3 ^ ^ +</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import tables, strutils, strformat
type operator = tuple[prec:int, rassoc:bool]
let ops = newTable[string, operator](
[ ("^", (4, true )),
("*", (3, false)),
("/", (3, false)),
("+", (2, false)),
("-", (2, false)) ])
proc shuntRPN(tokens:seq[string]): string =
var stack: seq[string]
var op:string
for token in tokens:
case token
of "(": stack.add token
of ")":
while stack.len > 0:
op = stack.pop()
if op == "(": break
result &= op & " "
else:
if token in ops:
while stack.len > 0:
op = stack[^1] # peek stack top
if not (op in ops): break
if ops[token].prec > ops[op].prec or (ops[token].rassoc and (ops[token].prec == ops[op].prec)):
break
discard stack.pop()
result &= op & " "
stack.add token
else:
result &= token & " "
echo fmt"""{token:5} {join(stack," "):18} {result:25} """
while stack.len > 0:
result &= stack.pop() & " "
echo fmt""" {join(stack," "):18} {result:25} """
let input = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
echo &"for infix expression: '{input}' \n", "\nTOKEN OP STACK RPN OUTPUT"
echo "postfix: ", shuntRPN(input.strip.split)</syntaxhighlight>
{{out}}
<pre>for infix expression: '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
TOKEN OP STACK RPN OUTPUT
3 3
+ + 3
4 + 3 4
* + * 3 4
2 + * 3 4 2
/ + / 3 4 2 *
( + / ( 3 4 2 *
1 + / ( 3 4 2 * 1
- + / ( - 3 4 2 * 1
5 + / ( - 3 4 2 * 1 5
) + / 3 4 2 * 1 5 -
^ + / ^ 3 4 2 * 1 5 -
2 + / ^ 3 4 2 * 1 5 - 2
^ + / ^ ^ 3 4 2 * 1 5 - 2
3 + / ^ ^ 3 4 2 * 1 5 - 2 3
+ / ^ 3 4 2 * 1 5 - 2 3 ^
+ / 3 4 2 * 1 5 - 2 3 ^ ^
+ 3 4 2 * 1 5 - 2 3 ^ ^ /
3 4 2 * 1 5 - 2 3 ^ ^ / +
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|OCaml}}==
{{works with|ocaml|4.04}}
<
type associativity = Left | Right;;
Line 2,205 ⟶ 3,477:
let postfix = shunting_yard tkns in
print_endline (intercalate " " postfix);;
</syntaxhighlight>
=={{header|Perl}}==
{{trans|
<
'^' => 4,
'*' => 3,
Line 2,258 ⟶ 3,530:
local $, = " ";
print shunting_yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';
</syntaxhighlight>
{{out}}
<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 2,280 ⟶ 3,552:
3 4 2 * 1 5 - 2 3 ^ ^ + reduce /
3 4 2 * 1 5 - 2 3 ^ ^ / reduce +
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|Phix}}==
{{Trans|Go}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #008080;">constant</span> <span style="color: #000000;">operators</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"^"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"*"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"/"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">precedence</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span> <span style="color: #0000FF;">}</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">infix</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rpn</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sep</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">stack_top</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
<span style="color: #000000;">ops</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">substitute_all</span><span style="color: #0000FF;">(</span><span style="color: #000000;">infix</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"("</span><span style="color: #0000FF;">,</span><span style="color: #008000;">")"</span><span style="color: #0000FF;">},{</span><span style="color: #008000;">" ( "</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" ) "</span><span style="color: #0000FF;">}),</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Infix input: %-32s%s"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">infix</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">show_workings</span><span style="color: #0000FF;">?</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">:</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ops</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ops</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"("</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">")"</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">stack_top</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[$]</span>
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">stack_top</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"("</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">sep</span><span style="color: #0000FF;">&</span><span style="color: #000000;">stack_top</span>
<span style="color: #000000;">sep</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" "</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">operators</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">prec</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">precedence</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">stack_top</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[$]</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack_top</span><span style="color: #0000FF;">,</span><span style="color: #000000;">operators</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">prec</span><span style="color: #0000FF;">></span><span style="color: #000000;">precedence</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">prec</span><span style="color: #0000FF;">=</span><span style="color: #000000;">precedence</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">and</span> <span style="color: #000000;">stack_top</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"^"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">sep</span><span style="color: #0000FF;">&</span><span style="color: #000000;">stack_top</span>
<span style="color: #000000;">sep</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" "</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">)</span>
<span
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">sep</span><span style="color: #0000FF;">&</span><span style="color: #000000;">op</span>
<span style="color: #000000;">sep</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" "</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">show_workings</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?{</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">sep</span><span style="color: #0000FF;">&</span><span style="color: #000000;">op</span>
<span style="color: #000000;">sep</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" "</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"result: %-22s [%s]\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">=</span><span style="color: #000000;">rpn</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"ok"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"**ERROR**"</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3 + 4 * 2 / (1 - 5) ^ 2 ^ 3"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3 4 2 * 1 5 - 2 3 ^ ^ / +"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">show_workings</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"((1 + 2) ^ (3 + 4)) ^ (5 + 6)"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 2 + 3 4 + ^ 5 6 + ^"</span><span
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"(1 + 2) ^ (3 + 4) ^ (5 + 6)"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 2 + 3 4 + 5 6 + ^ ^"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"((3 ^ 4) ^ 2 ^ 9) ^ 2 ^ 5"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3 4 ^ 2 9 ^ ^ 2 5 ^ ^"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"(1 + 4) * (5 + 3) * 2 * 3"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 4 + 5 3 + * 2 * 3 *"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 * 2 * 3 * 4"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 2 * 3 * 4 *"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 + 2 + 3 + 4"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 2 + 3 + 4 +"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"(1 + 2) ^ (3 + 4)"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 2 + 3 4 + ^"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"(5 ^ 6) ^ 7"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5 6 ^ 7 ^"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"5 ^ 4 ^ 3 ^ 2"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5 4 3 2 ^ ^ ^"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 + 2 + 3"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 2 + 3 +"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 ^ 2 ^ 3"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 2 3 ^ ^"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"(1 ^ 2) ^ 3"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 2 ^ 3 ^"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 - 1 + 3"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 1 - 3 +"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3 + 1 - 1"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3 1 + 1 -"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1 - (2 + 3)"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1 2 3 + -"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"4 + 3 + 2"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4 3 + 2 +"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"5 + 4 + 3 + 2"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5 4 + 3 + 2 +"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"5 * 4 * 3 * 2"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5 4 * 3 * 2 *"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"5 + 4 - (3 + 2)"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5 4 + 3 2 + -"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3 - 4 * 5"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3 4 5 * -"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"3 * (4 - 5)"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3 4 5 - *"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">shunting_yard</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"(3 - 4) * 5"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3 4 - 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"</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,490 ⟶ 3,694:
=={{header|PicoLisp}}==
Note: "^" is a meta-character and must be escaped in strings
<
(member Op '("\^" "*" "/" "+" "-")) )
Line 2,530 ⟶ 3,734:
(quit "Unbalanced Stack") )
(link (pop 'Stack))
(tab Fmt NIL (glue " " (made)) Stack) ) ) ) )</
Output:
<
Token Output Stack
3 3
Line 2,553 ⟶ 3,757:
3 4 2 * 1 5 - 2 3 ^ ^ / +
3 4 2 * 1 5 - 2 3 ^ ^ / +
-> (3 4 2 "*" 1 5 "-" 2 3 "\^" "\^" "/" "+")</
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
cvt: procedure options (main); /* 15 January 2012. */
declare (in, stack, out) character (100) varying;
Line 2,639 ⟶ 3,843:
end cvt;
</syntaxhighlight>
Output:
<syntaxhighlight lang="text">
INPUT STACK OUTPUT
3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) (
Line 2,674 ⟶ 3,878:
3 4 2 * 1 5 - 2 3 ^ ^ / +
3 4 2 * 1 5 - 2 3 ^ ^ / +
</syntaxhighlight>
=={{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
Line 2,781 ⟶ 3,985:
print( ' '.join('{cell:<{width}}'.format(width=width, cell=cell) for (width, cell) in zip(maxcolwidths, row)))
print('\n The final output RPN is: %r' % rp[-1][2])</
;Sample output:
Line 2,813 ⟶ 4,017:
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
;print column of width w
Line 2,858 ⟶ 4,062:
((if (lasso? x) <= <) (prec x) (prec y)))))])
(shunt (append (reverse l) out) (cons x r) in (format "out ~a, push ~a" l x)))])])))
</syntaxhighlight>
{{out}}
<pre>
Line 2,880 ⟶ 4,084:
'("3" "4" "2" "*" "1" "5" "-" "2" "3" "^" "^" "/" "+")
</pre>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line> my %prec =
'^' => 4,
'*' => 3,
'/' => 3,
'+' => 2,
'-' => 2,
'(' => 1;
my %assoc =
'^' => 'right',
'*' => 'left',
'/' => 'left',
'+' => 'left',
'-' => 'left';
sub shunting-yard ($prog) {
my @inp = $prog.words;
my @ops;
my @res;
sub report($op) { printf "%25s %-7s %10s %s\n", ~@res, ~@ops, $op, ~@inp }
sub shift($t) { report( "shift $t"); @ops.push: $t }
sub reduce($t) { report("reduce $t"); @res.push: $t }
while @inp {
given @inp.shift {
when /\d/ { reduce $_ };
when '(' { shift $_ }
when ')' { while @ops and (my $x = @ops.pop and $x ne '(') { reduce $x } }
default {
my $newprec = %prec{$_};
while @ops {
my $oldprec = %prec{@ops[*-1]};
last if $newprec > $oldprec;
last if $newprec == $oldprec and %assoc{$_} eq 'right';
reduce @ops.pop;
}
shift $_;
}
}
}
reduce @ops.pop while @ops;
@res;
}
say shunting-yard '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3';</syntaxhighlight>
{{out}}
<pre> reduce 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
3 shift + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
3 + reduce 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
3 4 + shift * 2 / ( 1 - 5 ) ^ 2 ^ 3
3 4 + * reduce 2 / ( 1 - 5 ) ^ 2 ^ 3
3 4 2 + reduce * ( 1 - 5 ) ^ 2 ^ 3
3 4 2 * + shift / ( 1 - 5 ) ^ 2 ^ 3
3 4 2 * + / shift ( 1 - 5 ) ^ 2 ^ 3
3 4 2 * + / ( reduce 1 - 5 ) ^ 2 ^ 3
3 4 2 * 1 + / ( shift - 5 ) ^ 2 ^ 3
3 4 2 * 1 + / ( - reduce 5 ) ^ 2 ^ 3
3 4 2 * 1 5 + / ( reduce - ^ 2 ^ 3
3 4 2 * 1 5 - + / shift ^ 2 ^ 3
3 4 2 * 1 5 - + / ^ reduce 2 ^ 3
3 4 2 * 1 5 - 2 + / ^ shift ^ 3
3 4 2 * 1 5 - 2 + / ^ ^ reduce 3
3 4 2 * 1 5 - 2 3 + / ^ reduce ^
3 4 2 * 1 5 - 2 3 ^ + / reduce ^
3 4 2 * 1 5 - 2 3 ^ ^ + reduce /
3 4 2 * 1 5 - 2 3 ^ ^ / reduce +
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|REXX}}==
These REXX versions below allow multi-character tokens (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.*/
Line 2,935 ⟶ 4,210:
/*──────────────────────────────────────────────────────────────────────────────────────────*/
isOp: return pos(arg(1),rOp) \== 0 /*is the first argument a "real" operator? */
show: if tell then say center(?,5) left(subword(x,k),L) left($,L%2) left(RPN,L) arg(1); return</
'''output''' when using the default input:
<pre>
Line 2,975 ⟶ 4,250:
The '''select''' 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.*/
Line 3,031 ⟶ 4,306:
/*──────────────────────────────────────────────────────────────────────────────────────────*/
isOp: return pos(arg(1), Rop) \== 0 /*is the first argument a "real" operator? */
show: if tell then say center(?,5) left(subword(x,k),L) left($,L%2) left(RPN,L) arg(1); return</
'''output''' when using the input: <tt> ) ( </tt>
<pre>
input: ) (
RPN──► ─────── error in expression ───────
</pre>
=={{header|RPL}}==
≪ "§" + → expression
≪ { }
1 expression SIZE '''FOR''' j
DUP TYPE NOT <span style="color:grey">@ 1 if a number is in top-stack position</span>
expression j DUP SUB
'''IF''' "0123456789" OVER POS '''THEN'''
STR→
'''IF''' SWAP '''THEN''' SWAP 10 * + '''END'''
'''ELSE'''
'''IF''' SWAP '''THEN''' ROT ROT + SWAP '''END'''
'''IF''' "^*/+-()" OVER POS '''THEN''' + '''ELSE''' DROP '''END'''
'''END'''
'''NEXT'''
≫ ≫ ‘<span style="color:blue">LEXER</span>’ STO <span style="color:grey">@ ( "1+(2*3)" → { 1 "+" "(" 2 "*" 3 ")" } )</span>
≪ '''IF''' OVER '''THEN'''
"^*/+-" DUP 5 PICK POS SWAP ROT POS
{ 4 3 3 2 2 } { 1 0 0 0 0 }
→ o2 o1 prec rasso
≪ '''IF''' o2 '''THEN'''
prec o1 GET prec o2 GET
'''IF''' rasso o1 GET '''THEN''' < '''ELSE''' ≤ '''END'''
'''ELSE''' 0 '''END'''
≫
'''ELSE''' DROP 0 '''END'''
≫ ‘<span style="color:blue">POPOP?</span>’ STO <span style="color:grey">@ ( op → Boolean )</span>
≪ <span style="color:blue">LEXER</span> { } "" → infix postfix token
≪ 0
1 infix SIZE '''FOR''' j
infix j GET 'token' STO
1 SF
'''CASE'''
"^*/+-" token →STR POS '''THEN'''
1 CF
'''WHILE''' token <span style="color:blue">POPOP?</span> '''REPEAT'''
'postfix' ROT STO+ 1 - '''END'''
token SWAP 1 + '''END'''
"(" token == '''THEN'''
token SWAP 1 + '''END'''
")" token == '''THEN'''
'''WHILE''' DUP 1 FS? AND '''REPEAT'''
'''IF''' OVER "(" ≠ '''THEN'''
'postfix' ROT STO+
'''ELSE''' SWAP DROP 1 CF '''END'''
1 -
'''END'''
'''END'''
1 FS? '''THEN''' 'postfix' token STO+ '''END'''
'''END'''
'''NEXT'''
'''WHILE''' DUP '''REPEAT'''
'postfix' ROT STO+
1 - '''END'''
DROP ""
1 postfix SIZE '''FOR''' j
postfix j GET + " " + '''NEXT'''
≫ ≫ ‘<span style="color:blue">→RPN<span>’ STO
"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" <span style="color:blue">→RPN<span>
{{out}}
<pre>
1: "3 4 2 * 1 5 - 2 3 ^ ^ / + "
</pre>
Line 3,041 ⟶ 4,382:
See [[Parsing/RPN/Ruby]]
<
outputs
<pre>for Infix expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Line 3,063 ⟶ 4,404:
3 PUSH V ["3", "4", "2", "*", "1", "5", "-", "2", "3"] ["+", "/", "^", "^"]
RPN = 3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">type Number = f64;
#[derive(Debug, Copy, Clone, PartialEq)]
struct Operator {
token: char,
operation: fn(Number, Number) -> Number,
precedence: u8,
is_left_associative: bool,
}
#[derive(Debug, Clone, PartialEq)]
enum Token {
Digit(Number),
Operator(Operator),
LeftParen,
RightParen,
}
impl Operator {
fn new_token(
token: char,
precedence: u8,
is_left_associative: bool,
operation: fn(Number, Number) -> Number,
) -> Token {
Token::Operator(Operator {
token: token,
operation: operation,
precedence: precedence,
is_left_associative,
})
}
fn apply(&self, x: Number, y: Number) -> Number {
(self.operation)(x, y)
}
}
trait Stack<T> {
fn top(&self) -> Option<T>;
}
impl<T: Clone> Stack<T> for Vec<T> {
fn top(&self) -> Option<T> {
if self.is_empty() {
return None;
}
self.last().cloned()
}
}
fn lex_token(input: char) -> Result<Token, char> {
let ret = match input {
'0'...'9' => Token::Digit(input.to_digit(10).unwrap() as Number),
'+' => Operator::new_token('+', 1, true, |x, y| x + y),
'-' => Operator::new_token('-', 1, true, |x, y| x - y),
'*' => Operator::new_token('*', 2, true, |x, y| x * y),
'/' => Operator::new_token('/', 2, true, |x, y| x / y),
'^' => Operator::new_token('^', 3, false, |x, y| x.powf(y)),
'(' => Token::LeftParen,
')' => Token::RightParen,
_ => return Err(input),
};
Ok(ret)
}
fn lex(input: String) -> Result<Vec<Token>, char> {
input
.chars()
.filter(|c| !c.is_whitespace())
.map(lex_token)
.collect()
}
fn tilt_until(operators: &mut Vec<Token>, output: &mut Vec<Token>, stop: Token) -> bool {
while let Some(token) = operators.pop() {
if token == stop {
return true;
}
output.push(token)
}
false
}
fn shunting_yard(tokens: Vec<Token>) -> Result<Vec<Token>, String> {
let mut output: Vec<Token> = Vec::new();
let mut operators: Vec<Token> = Vec::new();
for token in tokens {
match token {
Token::Digit(_) => output.push(token),
Token::LeftParen => operators.push(token),
Token::Operator(operator) => {
while let Some(top) = operators.top() {
match top {
Token::LeftParen => break,
Token::Operator(top_op) => {
let p = top_op.precedence;
let q = operator.precedence;
if (p > q) || (p == q && operator.is_left_associative) {
output.push(operators.pop().unwrap());
} else {
break;
}
}
_ => unreachable!("{:?} must not be on operator stack", token),
}
}
operators.push(token);
}
Token::RightParen => {
if !tilt_until(&mut operators, &mut output, Token::LeftParen) {
return Err(String::from("Mismatched ')'"));
}
}
}
}
if tilt_until(&mut operators, &mut output, Token::LeftParen) {
return Err(String::from("Mismatched '('"));
}
assert!(operators.is_empty());
Ok(output)
}
fn calculate(postfix_tokens: Vec<Token>) -> Result<Number, String> {
let mut stack = Vec::new();
for token in postfix_tokens {
match token {
Token::Digit(number) => stack.push(number),
Token::Operator(operator) => {
if let Some(y) = stack.pop() {
if let Some(x) = stack.pop() {
stack.push(operator.apply(x, y));
continue;
}
}
return Err(format!("Missing operand for operator '{}'", operator.token));
}
_ => unreachable!("Unexpected token {:?} during calculation", token),
}
}
assert!(stack.len() == 1);
Ok(stack.pop().unwrap())
}
fn run(input: String) -> Result<Number, String> {
let tokens = match lex(input) {
Ok(tokens) => tokens,
Err(c) => return Err(format!("Invalid character: {}", c)),
};
let postfix_tokens = match shunting_yard(tokens) {
Ok(tokens) => tokens,
Err(message) => return Err(message),
};
calculate(postfix_tokens)
}</syntaxhighlight>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
import scala.util.control.Breaks._
object ShuntingYard {
def main(args: Array[String]): Unit = {
val infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
println(s"infix: $infix")
println(s"postfix: ${infixToPostfix(infix)}")
}
def infixToPostfix(infix: String): String = {
val ops = "-+/*^"
val sb = new StringBuilder
val s = scala.collection.mutable.Stack[Int]()
infix.split("\\s").foreach { token =>
if (token.nonEmpty) {
val c = token.head
val idx = ops.indexOf(c)
if (idx != -1) {
if (s.isEmpty) s.push(idx)
else {
breakable({
while (s.nonEmpty) {
val prec2 = s.top / 2
val prec1 = idx / 2
if (prec2 > prec1 || (prec2 == prec1 && c != '^')) sb.append(ops(s.pop)).append(' ')
else break
}
});
s.push(idx)
}
} else if (c == '(') {
s.push(-2) // -2 stands for '('
} else if (c == ')') {
// until '(' on stack, pop operators.
while (s.top != -2) sb.append(ops(s.pop)).append(' ')
s.pop()
} else {
sb.append(token).append(' ')
}
}
}
while (s.nonEmpty) sb.append(ops(s.pop)).append(' ')
sb.toString
}
}
</syntaxhighlight>
{{out}}
<pre>
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
</pre>
=={{header|Sidef}}==
{{trans|
<
'^' => 4,
'*' => 3,
Line 3,123 ⟶ 4,686:
}
say shunting_yard('3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3').join(' ')</
{{out}}
<pre>
Line 3,150 ⟶ 4,713:
=={{header|Standard ML}}==
<
datatype associativity = LEFT | RIGHT
type operator = { symbol : char, assoc : associativity, precedence : int }
Line 3,259 ⟶ 4,822:
parse' tokens [] []
end
end</
=={{header|Swift}}==
<syntaxhighlight lang="swift">// Updated to Swift 5.7
import Foundation
// Using arrays for both stack and queue
struct Stack<T> {
var isEmpty: Bool {
elements.isEmpty
}
var top: T? {
elements.last
}
mutating func push(_ newElement: T) {
elements.append(newElement)
}
mutating func pop() -> T? {
self.isEmpty ? nil : elements.removeLast()
}
}
struct Queue<T> {
var isEmpty: Bool {
elements.isEmpty
}
mutating func enqueue(_ newElement: T) {
elements.append(newElement)
}
mutating func dequeue() -> T {
return elements.removeFirst()
}
}
enum Associativity {
case Left, Right
}
// Protocol can be used to restrict Set extension
protocol OperatorType: Comparable, Hashable {
}
struct Operator: OperatorType {
// Duplicate operator names are not allowed
func hash(into hasher: inout Hasher) {
hasher.combine(self.name)
}
init(_ name: String, _ precedence: Int, _ associativity: Associativity) {
self.name = name; self.precedence = precedence; self.associativity = associativity
}
}
func ==(x: Operator, y: Operator) -> Bool {
// Identified by name
}
func <(x: Operator, y: Operator) -> Bool {
}
extension Set where Element: OperatorType {
contains { $0.name
}
subscript (operatorName: String) -> Element? {
get {
filter { $0.name == operatorName }.first
}
}
}
// Convenience
extension String {
}
struct ShuntingYard {
case MismatchedParenthesis(parenthesis: String, expression: String)
case UnrecognizedToken(token: String, expression: String)
case ExtraneousToken(token: String, expression: String)
}
static func parse(_ input: String, operators: Set<Operator>) throws -> String {
var stack = Stack<String>()
var output = Queue<String>()
let tokens = input.components(separatedBy: " ")
for token in tokens {
// Number?
if token.isNumber {
// Add it to the output queue
output.enqueue(token)
continue
}
// Operator?
if operators.contains(token) {
// While there is a operator on top of the stack and has lower precedence than current operator (token)
while let top = stack.top,
operators.contains(top) && Self.hasLowerPrecedence(token, top, operators) {
// Pop it off to the output queue
output.enqueue(stack.pop()!)
}
// Push current operator (token) onto the operator stack
stack.push(token)
continue
}
// Left parenthesis?
if token == "(" {
// Push it onto the stack
stack.push(token)
continue
}
// Right parenthesis?
if token == ")" {
// Until the token at the top of the stack is a left parenthesis
while let top = stack.top, top != "(" {
// Pop operators off the stack onto the output queue.
output.enqueue(stack.pop()!)
}
// Pop the left parenthesis from the stack without putting it onto the output queue
guard let _ = stack.pop() else {
// If the stack runs out, than there is no matching left parenthesis
throw ParseError.MismatchedParenthesis(parenthesis: ")", expression: input)
}
continue
}
// Token not recognized!
throw ParseError.UnrecognizedToken(token: token, expression: token)
}
// No more tokens
// Still operators on the stack?
while let top = stack.top,
operators.contains(top) {
// Put them onto the output queue
output.enqueue(stack.pop()!)
}
// If the top of the stack is a (left) parenthesis, then there is no matching right parenthesis
// Note: Assume that all operators has been popped and put onto the output queue
if let top = stack.pop() {
throw (
top == "("
? ParseError.MismatchedParenthesis(parenthesis: "(", expression: input)
: ParseError.ExtraneousToken(token: top, expression: input)
)
}
return output.elements.joined(separator: " ")
}
static private func hasLowerPrecedence(_ firstToken: String, _ secondToken: String, _ operators: Set<Operator>) -> Bool {
guard let firstOperator = operators[firstToken],
let secondOperator = operators[secondToken] else {
return false
}
return firstOperator < secondOperator
}
}
/* Include in tests
func testParse() throws {
let input = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
let operators: Set<Operator> = [
Operator("^", 4, .Right),
Operator("*", 3, .Left),
Operator("/", 3, .Left),
Operator("+", 2, .Left),
Operator("-", 2, .Left)
]
let output = try! ShuntingYard.parse(input, operators: operators)
XCTAssertEqual(output, "3 4 2 * 1 5 - 2 3 ^ ^ / +")
}
*/
</syntaxhighlight>
{{out}}
<pre>
Line 3,445 ⟶ 5,033:
=={{header|Tcl}}==
<
# Helpers
Line 3,502 ⟶ 5,090:
}
puts [shunting "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"]</
Output:
<pre>
Line 3,557 ⟶ 5,145:
</pre>
=={{header|UNIX Shell}}==
<syntaxhighlight lang="bash">#!/bin/sh
getopprec() {
case "$1" in
'+') echo 2;;
'-') echo 2;;
'*') echo 3;;
'/') echo 4;;
'%') echo 4;;
'^') echo 4;;
'(') echo 5;;
esac
}
getopassoc() {
case "$1" in
'^') echo r;;
*) echo l;;
esac
}
showstacks() {
[ -n "$1" ] && echo "Token: $1" || echo "End parsing"
echo -e "\tOutput: `tr $'\n' ' ' <<< "$out"`"
echo -e "\tOperators: `tr $'\n' ' ' <<< "$ops"`"
}
infix() {
local out="" ops=""
while [ "$#" -gt 0 ]; do
grep -qE '^[0-9]+$' <<< "$1"
if [ "$?" -eq 0 ]; then
out="`sed -e '$a'"$1" -e '/^$/d' <<< "$out"`"
showstacks "$1"
shift && continue
fi
grep -q '^[-+*/^%]$' <<< "$1"
if [ "$?" -eq 0 ]; then
if [ -n "$ops" ]; then
thispred=`getopprec "$1"`
thisassoc=`getopassoc "$1"`
topop="`sed -n '$p' <<< "$ops"`"
thatpred=`getopprec "$topop"`
thatassoc=`getopassoc "$topop"`
while [ $thatpred -gt $thispred ] 2> /dev/null || ( [ \
$thatpred -eq $thispred ] 2> /dev/null && [ $thisassoc = \
'l' ] 2> /dev/null ); do # To /dev/null 'cus u r fake news
[ "$topop" = '(' ] && break
op="`sed -n '$p' <<< "$ops"`"
out="`sed -e '$a'"$op" -e '/^$/d' <<< "$out"`"
ops="`sed '$d' <<< "$ops"`"
topop="`sed -n '$p' <<< "$ops"`"
thatpred=`getopprec "$topop"`
thatassoc=`getopassoc "$topop"`
done
fi
ops="`sed -e '$a'"$1" -e '/^$/d' <<< "$ops"`"
showstacks "$1"
shift && continue
fi
if [ "$1" = '(' ]; then
ops="`sed -e '$a'"$1" -e '/^$/d' <<< "$ops"`"
showstacks "$1"
shift && continue
fi
if [ "$1" = ')' ]; then
grep -q '^($' <<< "`sed -n '$p' <<< "$ops"`"
while [ "$?" -ne 0 ]; do
op="`sed -n '$p' <<< "$ops"`"
out="`sed -e '$a'"$op" -e '/^$/d' <<< "$out"`"
ops="`sed '$d' <<< "$ops"`"
grep -q '^($' <<< "`sed '$p' <<< "$ops"`"
done
ops="`sed '$d' <<< "$ops"`"
showstacks "$1"
shift && continue
fi
shift
done
while [ -n "$ops" ]; do
op="`sed -n '$p' <<< "$ops"`"
out="`sed -e '$a'"$op" -e '/^$/d' <<< "$out"`"
ops="`sed '$d' <<< "$ops"`"
done
showstacks "$1"
}
infix 3 + 4 \* 2 / \( 1 - 5 \) ^ 2 ^ 3</syntaxhighlight>
===Output===
<syntaxhighlight lang="text">Token: 3
Output: 3
Operators:
Token: +
Output: 3
Operators: +
Token: 4
Output: 3 4
Operators: +
Token: *
Output: 3 4
Operators: + *
Token: 2
Output: 3 4 2
Operators: + *
Token: /
Output: 3 4 2
Operators: + * /
Token: (
Output: 3 4 2
Operators: + * / (
Token: 1
Output: 3 4 2 1
Operators: + * / (
Token: -
Output: 3 4 2 1
Operators: + * / ( -
Token: 5
Output: 3 4 2 1 5
Operators: + * / ( -
Token: )
Output: 3 4 2 1 5 -
Operators: + * /
Token: ^
Output: 3 4 2 1 5 -
Operators: + * / ^
Token: 2
Output: 3 4 2 1 5 - 2
Operators: + * / ^
Token: ^
Output: 3 4 2 1 5 - 2
Operators: + * / ^ ^
Token: 3
Output: 3 4 2 1 5 - 2 3
Operators: + * / ^ ^
End parsing
Output: 3 4 2 1 5 - 2 3 ^ ^ / * +
Operators:</syntaxhighlight>
=={{header|VBA}}==
Line 3,562 ⟶ 5,305:
{{trans|Liberty BASIC}}
<
Option Base 1
Line 3,671 ⟶ 5,414:
Function Peek(stack)
Peek = stack(UBound(stack))
End Function</
{{out}}
Line 3,694 ⟶ 5,437:
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|
{{trans|
<syntaxhighlight lang="vbnet">Module Module1
Class SymbolType
Public ReadOnly symbol As String
Public ReadOnly precedence As Integer
Public ReadOnly rightAssociative As Boolean
Public Sub New(symbol As String, precedence As Integer, rightAssociative As Boolean)
Me.symbol = symbol
Me.precedence = precedence
Me.rightAssociative = rightAssociative
End Class
ReadOnly Operators As Dictionary(Of String, SymbolType) = New Dictionary(Of String, SymbolType) From
{
{"^", New SymbolType("^", 4, True)},
{"*", New SymbolType("*", 3, False)},
{"/", New SymbolType("/", 3, False)},
{"+", New SymbolType("+", 2, False)},
{"-", New SymbolType("-", 2, False)}
}
Function ToPostfix(infix As String) As String
Dim tokens = infix.Split(" ")
Dim stack As New Stack(Of String)
Dim output As New List(Of String)
Dim Print = Sub(action As String) Console.WriteLine("{0,-4} {1,-18} {2}", action + ":", $"stack[ {String.Join(" ", stack.Reverse())} ]", $"out[ {String.Join(" ", output)} ]")
For Each token In tokens
Dim iv As Integer
Dim op1 As SymbolType
Dim op2 As SymbolType
If Integer.TryParse(token, iv) Then
output.Add(token)
Print(token)
ElseIf Operators.TryGetValue(token, op1) Then
While stack.Count > 0 AndAlso Operators.TryGetValue(stack.Peek(), op2)
Dim c = op1.precedence.CompareTo(op2.precedence)
If c < 0 OrElse Not op1.rightAssociative AndAlso c <= 0 Then
output.Add(stack.Pop())
Else
Exit While
End If
End While
stack.Push(token)
Print(token)
ElseIf token = "(" Then
stack.Push(token)
Print(token)
ElseIf token = ")" Then
Dim top = ""
While stack.Count > 0
top = stack.Pop()
If top <> "(" Then
output.Add(top)
Else
Exit While
End If
End While
If top <> "(" Then
Throw New ArgumentException("No matching left parenthesis.")
End If
Print(token)
End If
Next
While stack.Count > 0
Dim top = stack.Pop()
If Not Operators.ContainsKey(top) Then
Throw New ArgumentException("No matching right parenthesis.")
End If
output.Add(top)
End While
Print("pop")
Return String.Join(" ", output)
End Function
Sub Main()
Dim infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3"
Console.WriteLine(ToPostfix(infix))
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>3: stack[ ] out[ 3 ]
+: stack[ + ] out[ 3 ]
4: stack[ + ] out[ 3 4 ]
*: stack[ + * ] out[ 3 4 ]
2: stack[ + * ] out[ 3 4 2 ]
/: stack[ + / ] out[ 3 4 2 * ]
(: stack[ + / ( ] out[ 3 4 2 * ]
1: stack[ + / ( ] out[ 3 4 2 * 1 ]
-: stack[ + / ( - ] out[ 3 4 2 * 1 ]
5: stack[ + / ( - ] out[ 3 4 2 * 1 5 ]
): stack[ + / ] out[ 3 4 2 * 1 5 - ]
^: stack[ + / ^ ] out[ 3 4 2 * 1 5 - ]
2: stack[ + / ^ ] out[ 3 4 2 * 1 5 - 2 ]
^: stack[ + / ^ ^ ] out[ 3 4 2 * 1 5 - 2 ]
3: stack[ + / ^ ^ ] out[ 3 4 2 * 1 5 - 2 3 ]
pop: stack[ ] out[ 3 4 2 * 1 5 - 2 3 ^ ^ / + ]
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-seq}}
{{libheader|Wren-pattern}}
<syntaxhighlight lang="wren">import "./seq" for Stack
import "./pattern" for Pattern
/* To find out the precedence, we take the index of the
token in the OPS string and divide by 2 (rounding down).
This will give us: 0, 0, 1, 1, 2 */
var ops = "-+/*^"
var infixToPostfix = Fn.new { |infix|
var sb = ""
var s = Stack.new()
var p = Pattern.new("+1/s")
for (token in p.splitAll(infix)) {
var c = token[0]
var idx = ops.indexOf(c)
// check for operator
if (idx != - 1) {
if (s.isEmpty) {
s.push(idx)
} else {
while (!s.isEmpty) {
var prec2 = (s.peek()/2).floor
var prec1 = (idx/2).floor
if (prec2 > prec1 || (prec2 == prec1 && c != "^")) {
sb = sb + ops[s.pop()] + " "
} else break
}
s.push(idx)
}
} else if (c == "(") {
s.push(-2) // -2 stands for "("
} else if (c == ")") {
// until "(" on stack, pop operators.
while (s.peek() != -2) sb = sb + ops[s.pop()] + " "
s.pop()
} else {
sb = sb + token + " "
}
}
while (!s.isEmpty) sb = sb + ops[s.pop()] + " "
return sb
}
var es = [
"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3",
]
for (e in es) {
System.print("Infix : %(e)")
System.print("Postfix : %(infixToPostfix.call(e))\n")
}</syntaxhighlight>
{{out}}
<pre>
Postfix : 3 4 2 * 1 5 - 2 3 ^ ^ / +
Infix : ( ( 1 + 2 ) ^ ( 3 + 4 ) ) ^ ( 5 + 6 )
Postfix : 1 2 + 3 4 + ^ 5 6 + ^
</pre>
=={{header|Xojo}}==
Line 3,819 ⟶ 5,611:
{{trans|VBA}}
<syntaxhighlight lang="xojo">
Function ShuntingYard(strInfix As String) As String
Line 3,990 ⟶ 5,782:
End Function</
Line 4,015 ⟶ 5,807:
Output:
3 4 2 * 1 5 - 2 3 ^ ^ / +</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">int Stack(10);
int SP; \stack pointer
proc Push(N);
int N;
[Stack(SP):= N; SP:= SP+1];
func Pop;
[SP:= SP-1; return Stack(SP)];
func Precedence(Op);
int Op;
case Op of
^+, ^-: return 2;
^*, ^/: return 3;
^^: return 4
other [];
proc ShowStack;
int I;
[ChOut(0, 9\tab\);
for I:= 0 to SP-1 do
[ChOut(0, Stack(I)); ChOut(0, ^ )];
CrLf(0);
];
char Str;
int Token, Op1, Op2;
[Str:= "3 + 4 * 2 / ( 1 - 5 ) ^^ 2 ^^ 3 ";
SP:= 0;
Text(0, "Input Output Stack^m^j");
loop [repeat Token:= Str(0); Str:= Str+1;
until Token # ^ ; \skip space characters
if Token # $A0 \terminating space\ then
[ChOut(0, Token); ChOut(0, 9\tab\)];
case Token of
^+, ^-, ^*, ^/, ^^:
[Op1:= Token;
loop [if SP <= 0 then quit; \empty
Op2:= Stack(SP-1);
if Op2 = ^( then quit;
if Precedence(Op2) < Precedence(Op1) then quit;
if Precedence(Op2) = Precedence(Op1) then
if Op1 = ^^ then quit;
ChOut(0, Pop);
];
Push(Op1);
];
^(: Push(Token);
^): [while SP > 0 and Stack(SP-1) # ^( do
ChOut(0, Pop);
Pop; \discard left parenthesis
];
$A0: quit \terminating space with MSB set
other ChOut(0, Token); \print single digit number
ShowStack;
];
while SP > 0 do \print any remaining operators
[ChOut(0, 9\tab\);
ChOut(0, Pop);
ShowStack;
];
]</syntaxhighlight>
{{out}}
<pre>
Input Output Stack
3 3
+ +
4 4 +
* + *
2 2 + *
/ * + /
( + / (
1 1 + / (
- + / ( -
5 5 + / ( -
) - + /
^ + / ^
2 2 + / ^
^ + / ^ ^
3 3 + / ^ ^
^ + / ^
^ + /
/ +
+
</pre>
=={{header|zkl}}==
{{trans|Go}}
<syntaxhighlight lang="zkl">var input="3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
var opa=Dictionary("^",T(4,True), "*",T(3,False), // op:(prec,rAssoc)
"/",T(3,False), "+",T(2,False), "-",T(2,False),
);
"infix: ".println(input);
"postfix:".println(parseInfix(input));
fcn parseInfix(e){
stack:=List(); // holds operators and left parenthesis
rpn:="";
foreach tok in (e.split(" ")){
switch(tok){
case("("){ stack.append(tok) } // push "(" to stack
case(")"){
while(True){ // pop item ("(" or operator) from stack
op:=stack.pop();
if(op=="(") break; // discard "("
rpn+=" " + op; // add operator to result
}
}
else{ // default
o1:=opa.find(tok); // op or Void
if(o1){ // token is an operator
while(stack){
// consider top item on stack
op:=stack[-1]; o2:=opa.find(op);
if(not o2 or o1[0]>o2[0] or
(o1[0]==o2[0] and o1[1])) break;
// top item is an operator that needs to come off
stack.pop();
rpn+=" " + op; // add it to result
}
// push operator (the new one) to stack
stack.append(tok);
}else // token is an operand
rpn+=(rpn and " " or "") + tok; // add operand to result
}
} // switch
display(tok,rpn,stack);
} // foreach
// drain stack to result
rpn + stack.reverse().concat(" ");
}
fcn display(tok,rpn,stack){
"Token|".println(tok);
"Stack|".println(stack.concat());
"Queue|".println(rpn);
println();
}</syntaxhighlight>
{{out}}
<pre style="height:20ex;overflow:scroll;">
infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Token|3
Stack|
Queue|3
Token|+
Stack|+
Queue|3
Token|4
Stack|+
Queue|3 4
Token|*
Stack|+*
Queue|3 4
Token|2
Stack|+*
Queue|3 4 2
Token|/
Stack|+/
Queue|3 4 2 *
Token|(
Stack|+/(
Queue|3 4 2 *
Token|1
Stack|+/(
Queue|3 4 2 * 1
Token|-
Stack|+/(-
Queue|3 4 2 * 1
Token|5
Stack|+/(-
Queue|3 4 2 * 1 5
Token|)
Stack|+/
Queue|3 4 2 * 1 5 -
Token|^
Stack|+/^
Queue|3 4 2 * 1 5 -
Token|2
Stack|+/^
Queue|3 4 2 * 1 5 - 2
Token|^
Stack|+/^^
Queue|3 4 2 * 1 5 - 2
Token|3
Stack|+/^^
Queue|3 4 2 * 1 5 - 2 3
postfix:3 4 2 * 1 5 - 2 3^ ^ / +
</pre>
|