r/dailyprogrammer • u/nint22 1 2 • Oct 18 '12
[10/18/2012] Challenge #104 [Hard] (Stack Attack)
Description:
You are a devilish engineer designing a new programming language titled D++, which stands for a "Dijkstra++", named after your favorite computer scientist. You are currently working on the math-operations parsing component of your interpreter: though the language only supports infix-notation (such as "1 + 2 * 3"), your interpreter internals require you to represent all math strings in reverse polish notation (for easier, stack-based, computing). Your goal is to simply take a guaranteed valid infix-notation string of math operations and generate (printing it out) an equivalent and valid reverse polish notation string.
Formal Inputs & Outputs:
Input Description:
string MathOperations - A valid string of infix math notation.
Output Description:
Print the converted RPN form of the given math operations string.
Sample Inputs & Outputs:
"1 + 2" should be printed as "1 2 +". "(1+2)*3" should be printed as "3 2 1 + *". "(6 (7 – 2)) / 3 + 9 * 4" should be printed as "6 7 2 - * 3 / 9 4 * +".
Notes:
Do not get trapped in overly-complex solutions; there are formal solutions, though many ways of solving for this problem. Check out the Shunting Yard Algorithm for details on how to convert math-operation strings (a stack of tokens) from one notation system to another.
1
Oct 19 '12
Here's one in (vanilla) javascript. I didn't look up how to do it, but I'm sure my approach isn't unusual.
function in_to_post(infix) {
var OPERATORS = {'+': 1, '-': 1, '*': 2, '/': 2},
parens = 0,
blocks = [],
ops = [];
infix.replace(/\d+|\S/g, function (b, tmp) {
if (b === '(') {
parens++;
} else if (b === ')') {
parens--;
} else if (b in OPERATORS) {
b = new String(b);
b.priority = parens * 10 + OPERATORS[b];
while (ops.length && b.priority <= ops[ops.length - 1].priority) {
tmp = blocks.pop();
blocks.push(blocks.pop() + ' ' + tmp + ' ' + ops.pop());
}
ops.push(b);
} else {
blocks.push(b);
}
});
return blocks.concat(ops.reverse()).join(' ');
}2
u/nint22 1 2 Oct 19 '12
I've been waiting for one in Javascript - nicely done! It looks about right, and is a clean implementation. Nice!
3
2
u/akaicewolf Oct 18 '12
Why can't this have been posted earlier. Did this about two weeks ago for class
2
Oct 18 '12 edited Oct 19 '12
In ruby, using the shunting yard algorithm
#main reason for this class is the takes_precedence_over function
class Operator
attr_accessor :op, :paren_count
def initialize(op, paren_count)
@op, @paren_count = op, paren_count
end
#takes in to account nesting parenthesis and standard order of operations
def takes_precedence_over(oper)
if (@paren_count > oper.paren_count)
return 1
elsif oper.paren_count > @paren_count
return -1
elsif (@op == '*' or @op == '/') and (oper.op == '+' or oper.op == '-')
return 1
elsif (@op == '+' or @op == '-') and (oper.op == '*' or oper.op == '/')
return -1
else
return 0
end
end
end
def to_reverse_polish(infix_notation)
paren_count = 0
output_q = []
ops_stack = []
infix_arr = infix_notation.split(' ')
#iterating through all the symbols, using shunting algorithm
infix_arr.each do |sym|
if !('0'..'9').to_a.index(sym).nil? #number
output_q.push(sym)
elsif !%w{+ - * /}.index(sym).nil? #operator
oper = Operator.new(sym, paren_count)
if ops_stack.length != 0 and oper.takes_precedence_over(ops_stack[0]) != 1
#move contents of the operators stack to the output queue
while ops_stack.length > 0
output_q.push(ops_stack.shift.op)
end
ops_stack = []
end
ops_stack.insert(0, oper)
elsif sym == '('
paren_count = paren_count + 1
elsif sym == ')'
#move all operators of the current paren_count (before this close parenthesis)
# to the output queue
while ops_stack.length > 0 and ops_stack[0].paren_count == paren_count
output_q.push(ops_stack.shift.op)
end
paren_count = paren_count - 1
else
print 'Error: cannot parse ' + sym
end
end
#move any remaining operators to the output queue
while ops_stack.length > 0
output_q.push(ops_stack.shift.op)
end
return output_q.join(' ')
endTest cases:
puts to_reverse_polish('1 + 2')
puts to_reverse_polish('2 + 3 + 5')
puts to_reverse_polish('( 1 + 2 ) * 3')
puts to_reverse_polish('2 + ( 3 + 5 )')
puts to_reverse_polish('2 + ( 3 * ( 5 - 2 ) )')
puts to_reverse_polish('( 6 * ( 7 - 2 ) ) / 3 + 9 * 4')2
u/prophile Oct 19 '12
Implemented with peg.js:
start
= ws x:additive !. { return x; }
additive
= first:multiplicative second:addRest { return first + second; }
addRest
= operator:[+-] ws value:multiplicative rest:addRest { return " " + value + " " + operator + rest; }
/ "" { return ""; }
multiplicative
= first:primary second:mulRest { return first + second; }
mulRest
= operator:[*/] ws value:primary rest:mulRest { return " " + value + " " + operator + rest; }
/ "" { return ""; }
primary
= integer
/ "(" ws additive:additive ")" ws { return additive; }
integer "integer"
= digits:[0-9]+ ws { return parseInt(digits.join(""), 10); }
ws
= [ \n\r]*1
u/robin-gvx 0 2 Oct 19 '12 edited Oct 19 '12
Modified my solution for a different challenge: (which was to write a calculator)
is-number s:
try:
drop to-num s
true
catch value-error:
false
set :prec { "+" 1 "-" 1 "*" 2 "/" 2 }
shunting-yard text:
local :output-queue [] # it's implemented by using a stack and reversing it when done
local :stack []
for c in chars text:
if is-number c:
push-to output-queue c
elseif = "(" c:
push-to stack c
elseif = ")" c:
while != "(" dup pop-from stack:
push-to output-queue
drop
else: #just assume it's an operator
local :v true
while and stack v:
local :o2 pop-from stack
if = "(" o2:
push-to stack o2
set :v false
else:
if <= get-from prec c get-from prec o2:
push-to output-queue o2
else:
push-to stack o2
set :v false
push-to stack c
for op in stack:
push-to output-queue op
join " " reversed output-queue
print "Please enter a calculation:"
print shunting-yard input1
u/nerdcorerising Oct 20 '12
In C#, using a recursive descent parser approach. My answer should be correct except for "implied" multiplication, i.e. the example above that contains "(6 (7 - 2))" wouldn't parse right. It would with "(6 * (7 - 2))"
abstract class Expression
{
public abstract string postfix();
}
class BinaryExpression : Expression
{
private string op;
private Expression lhs;
private Expression rhs;
public BinaryExpression(string op, Expression lhs, Expression rhs)
{
this.op = op;
this.lhs = lhs;
this.rhs = rhs;
}
public override string postfix()
{
return String.Join(" ", this.lhs.postfix(), this.rhs.postfix(), this.op);
}
}
class Number : Expression
{
private string num;
public Number(string num)
{
this.num = num;
}
public override string postfix()
{
return this.num;
}
}
class Program
{
private static char[] operators = new char[] { '+', '-', '*', '/', '(', ')' };
static void Main(string[] args)
{
while (true)
{
Queue<string> tokens = tokenize(Console.ReadLine());
Expression e = parseExpression(tokens.Dequeue(), tokens);
Console.WriteLine(e.postfix());
}
}
static Queue<string> tokenize(string input)
{
Queue<string> tokens = new Queue<string>();
while (input.Count() > 0)
{
string next = getNextToken(ref input);
tokens.Enqueue(next);
}
return tokens;
}
static string getNextToken(ref string input)
{
input = input.Trim();
char ch = input[0];
if (isParensOrOperator(ch))
{
input = input.Substring(1);
return ch.ToString();
}
int i = 1;
while (i < input.Count() && (Char.IsDigit(input[i]) || input[i] == '.'))
{
i++;
}
string ret = input.Substring(0, i);
input = input.Substring(i);
return ret;
}
static bool isParensOrOperator(char ch)
{
return operators.Contains(ch);
}
static Expression parseExpression(string curr, Queue<string> tokens)
{
Expression lhs = parseTerm(curr, tokens);
if (tokens.Count() > 0)
{
string lookahead = tokens.Peek();
while (lookahead.Equals("+") || lookahead.Equals("-"))
{
lookahead = tokens.Dequeue();
lhs = new BinaryExpression(lookahead, lhs, parseTerm(tokens.Dequeue(), tokens));
lookahead = tokens.Count() > 0 ? tokens.Peek() : "";
}
}
return lhs;
}
static Expression parseTerm(string curr, Queue<string> tokens)
{
Expression lhs = parseFactor(curr, tokens);
if (tokens.Count() > 0)
{
string lookahead = tokens.Peek();
while (lookahead.Equals("*") || lookahead.Equals("/"))
{
lookahead = tokens.Dequeue();
lhs = new BinaryExpression(lookahead, lhs, parseTerm(tokens.Dequeue(), tokens));
lookahead = tokens.Count() > 0 ? tokens.Peek() : "";
}
}
return lhs;
}
static Expression parseFactor(string curr, Queue<string> tokens)
{
if (curr.Equals("("))
{
Expression middle = parseExpression(tokens.Dequeue(), tokens);
tokens.Dequeue(); // close parens
return middle;
}
return new Number(curr);
}
}1
u/efrey Oct 20 '12 edited Oct 20 '12
In Haskell using Precedence Climbing
import Prelude hiding ( exp )
import Control.Applicative ( (<*), (<*>), (<$>), pure )
import Control.Arrow ( (&&&) )
import Data.Function ( on )
import Control.Monad ( guard )
import Data.List ( intersperse )
import Text.Parsec
data Exp = Term String | Bin String Exp Exp
precedence b = if any (== b) [ '*', '/' ] then 2 else 1
tok = (<* spaces)
parens = (between `on` tok . char) '(' ')'
term = parens exp <|> Term <$> tok (many1 digit)
exp = e 0
bin = choice $ map (tok . char) "*/+-"
e p = next =<< term
where
next expr = try (go expr) <|> return expr
go e1 = do
( b, q ) <- (pure &&& precedence) <$> bin
guard (q >= p)
next . Bin b e1 =<< e q
toPostfix e = case e of
Term str -> str
Bin b e1 e2 -> concat $ intersperse " " [ toPostfix e1, toPostfix e2, b ]
postfixOf :: String -> String
postfixOf = either show toPostfix . parse exp ""1
u/altorelievo Oct 22 '12 edited Oct 23 '12
Not sure, if anybody will read this, being so late after the problem was posted. If anyone does, I think that this is somewhat similiar to the shunting algorithm. It doesn't work with parenthesis It doesn't use ^ or an implied * -- " 6 ( 7 + 3 )" would have to be " 6 * ( 7 + 3 )", any tips are welcomed :)
Python:
def RPN(equation):
ops = {'(':1, '-':2, '+':2, '*':3, '/':3}
stack = []
out = []
for token in equation:
if token.isdigit():
out.append(token)
else:
if len(stack) == 1 and token in ops and ops[token] <= ops[stack[-1]] and token != '(':
out.append(stack[-1])
stack.pop(-1)
stack.append(token)
elif token == '(':
stack.append(token)
elif len(stack) == 1 and token in ops and ops[token] >= ops[stack[-1]]:
stack.append(token)
elif len(stack) > 1 and token in ops and ops[token] < ops[stack[-1]]:
out.append(stack[-1])
stack.pop(-1)
out.append(stack[-1])
stack.pop(-1)
stack.append(token)
elif token == ')':
while stack[-1] != '(':
out.append(stack[-1])
stack.pop(-1)
stack.pop(-1)
elif len(stack) > 1 and token in ops and ops[token] >= ops[stack[-1]] and stack[-1] != '(':
out.append(stack[-1])
stack.pop(-1)
stack.append(token)
elif len(stack) > 1 and stack[-1] == '(' and token in ops:
stack.append(token)
elif len(stack) < 1 and token in ops:
stack.append(token)
if len(stack) > 0:
sorted(stack, key=ops.get)
stack = stack[::-1]
for token in stack:
out.append(token)
fin = ''
for i in out:
fin += ' ' + i
print fin
#print ''.join([i for i in out])1
u/tehbeard Nov 09 '12
Very late, but an implementation in java I wrote a few months back.
Version 2 of the class in the package also supports functions during parsing.
0
u/LOOKITSADAM 0 0 Oct 19 '12 edited Oct 19 '12
I'm trying to learn some functional programming, and here's my shot: Standard ML ,unable to handle parentheses, but everything else works.
fun splitAt ch str =
let
val a = "";
val b = hd (String.explode str);
val c = String.implode( tl (String.explode str));
fun chug (a, b, "") = (a,b,"")
| chug (a, b, c) = if b = ch then (a, b, c)
else chug(a^(Char.toString b),hd (String.explode c), String.implode(tl(String.explode c)));
in
chug(a,b,c)
end;
fun solvd str = case splitAt #"/" str of (a,#"/",b) => a^(solvd b)^("/")
| (a, ch, b) =>a^(Char.toString ch)^b;
fun solvt str = case splitAt #"*" str of (a,#"*",b) => (solvd a)^(solvt b)^("*")
| (a, ch, b) =>solvd (a^(Char.toString ch)^b);
fun solvm str = case splitAt #"-" str of (a,#"-",b) => (solvt a)^(solvm b)^("-")
| (a, ch, b) =>solvt (a^(Char.toString ch)^b);
fun solvp str = case splitAt #"+" str of (a,#"+",b) => (solvm a)^(solvp b)^("+")
| (a, ch, b) =>solvm (a^(Char.toString ch)^b);input:
solvp "6*2-7/3+9*4";output:
val it = "62*73/-94*+" : string
4
u/skeeto -9 8 Oct 18 '12 edited Oct 18 '12
In Emacs Lisp using the Shunting Yard Algorithm,
Your second example seems to be missing an operator, unless you intended to have implicit multiplication (in which case my code is wrong):