Anonymous user
Parsing/RPN to infix conversion: Difference between revisions
→{{header|AWK}}: Added AWK example.
(→{{header|Python}}: v4.1: documentation typo) |
(→{{header|AWK}}: Added AWK example.) |
||
Line 148:
((1 + 2) ^ (3 + 4)) ^ (5 + 6)
</pre>
=={{header|AWK}}==
Slavishly (mostly) follows TCL example.
<lang awk>#!/usr/bin/awk -f
BEGIN {
initStack()
initOpers()
print "Infix: " toInfix("3 4 2 * 1 5 - 2 3 ^ ^ / +")
print ""
print "Infix: " toInfix("1 2 + 3 4 + ^ 5 6 + ^")
}
function initStack() {
delete stack
stackPtr = 0
}
function initOpers() {
VALPREC = "9"
LEFT = "l"
RIGHT = "r"
operToks = "+" "-" "/" "*" "^"
operPrec = "2" "2" "3" "3" "4"
operAssoc = LEFT LEFT LEFT LEFT RIGHT
}
function toInfix(rpn, t, tok, a, ap, b, bp, tp, ta) {
print "Postfix: " rpn
gsub(/ +/, "", rpn)
for (t = 1; t <= length(rpn); t++) {
tok = substr(rpn, t, 1)
if (!isOper(tok)) {
push(VALPREC tok)
}
else {
b = pop()
bp = prec(b)
a = pop()
ap = prec(a)
tp = tokPrec(tok)
ta = tokAssoc(tok)
if (ap < tp || (ap == tp && ta == RIGHT)) {
a = "x(" tail(a) ")"
}
if (bp < tp || (bp == tp && ta == LEFT)) {
b = "x(" tail(b) ")"
}
push(tp tail(a) " " tok " " tail(b))
}
print " " tok " -> " stackToStr()
}
return tail(pop())
}
function push(expr) {
stack[stackPtr] = expr
stackPtr++
}
function pop() {
stackPtr--
return stack[stackPtr]
}
function isOper(tok) {
return index(operToks, tok) != 0
}
function prec(expr) {
return substr(expr, 1, 1)
}
function tokPrec(tok) {
return substr(operPrec, operIdx(tok), 1)
}
function tokAssoc(tok) {
return substr(operAssoc, operIdx(tok), 1)
}
function operIdx(tok) {
return index(operToks, tok)
}
function tail(s) {
return substr(s, 2)
}
function stackToStr( s, i, t, p) {
s = ""
for (i = 0; i < stackPtr; i++) {
t = stack[i]
p = prec(t)
if (index(t, " ")) t = "{" tail(t) "}"
else t = tail(t)
s = s "{" p " " t "} "
}
return s
}
</lang>
Output:
Postfix: 3 4 2 * 1 5 - 2 3 ^ ^ / +
3 -> {9 3}
4 -> {9 3} {9 4}
2 -> {9 3} {9 4} {9 2}
* -> {9 3} {3 {4 * 2}}
1 -> {9 3} {3 {4 * 2}} {9 1}
5 -> {9 3} {3 {4 * 2}} {9 1} {9 5}
- -> {9 3} {3 {4 * 2}} {2 {1 - 5}}
2 -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {9 2}
3 -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {9 2} {9 3}
^ -> {9 3} {3 {4 * 2}} {2 {1 - 5}} {4 {2 ^ 3}}
^ -> {9 3} {3 {4 * 2}} {4 {(1 - 5) ^ 2 ^ 3}}
/ -> {9 3} {3 {4 * 2 / (1 - 5) ^ 2 ^ 3}}
+ -> {2 {3 + 4 * 2 / (1 - 5) ^ 2 ^ 3}}
Infix: 3 + 4 * 2 / (1 - 5) ^ 2 ^ 3
Postfix: 1 2 + 3 4 + ^ 5 6 + ^
1 -> {9 1}
2 -> {9 1} {9 2}
+ -> {2 {1 + 2}}
3 -> {2 {1 + 2}} {9 3}
4 -> {2 {1 + 2}} {9 3} {9 4}
+ -> {2 {1 + 2}} {2 {3 + 4}}
^ -> {4 {(1 + 2) ^ (3 + 4)}}
5 -> {4 {(1 + 2) ^ (3 + 4)}} {9 5}
6 -> {4 {(1 + 2) ^ (3 + 4)}} {9 5} {9 6}
+ -> {4 {(1 + 2) ^ (3 + 4)}} {2 {5 + 6}}
^ -> {4 {((1 + 2) ^ (3 + 4)) ^ (5 + 6)}}
Infix: ((1 + 2) ^ (3 + 4)) ^ (5 + 6)
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
| |||