Parsing/Shunting-yard algorithm: Difference between revisions
Added C# 7 implementation
m (use named params) |
(Added C# 7 implementation) |
||
Line 558:
Testing string `123' <enter>
^C</pre>
=={{header|C sharp}}==
{{works with|C sharp|7.0}}
<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)} ]");
}
}</lang>
{{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|Ceylon}}==
Line 693 ⟶ 783:
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.
| |||