Parsing/Shunting-yard algorithm: Difference between revisions

=={{header|C++}}==

{{trans|Java}}

<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;

}</lang>

{{out}}

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

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

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

=={{header|Perl 6}}==

<lang perl6>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';</lang>

{{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 +

=={{header|zkl}}==

{{trans|Go}}

<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();

}</lang>

{{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>