Parsing/Shunting-yard algorithm: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 1,103: | Line 1,103: | ||
RPN:"3 4 2 * 1 5 - 2 3 ^ ^ / +" |
RPN:"3 4 2 * 1 5 - 2 3 ^ ^ / +" |
||
NIL</pre> |
NIL</pre> |
||
=={{header|D}}== |
|||
{{trans|Java}} |
|||
<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; |
|||
}</lang> |
|||
{{out}} |
|||
<pre>infix: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 |
|||
postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +</pre> |
|||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |