3 ms·
This post was an interesting one. I often get this problem in interviews, but never knew about this algorithm, so I implemented it and I love it! I also found
by parentheses 3y ago
This post was an interesting one. I often get this problem in interviews, but never knew about this algorithm, so I implemented it and I love it!
I also found that it's super-easy to extend to support parentheses.
Some Ruby code to share if anyone would like to see it.
PRECEDENCES = [
['+', '-'],
['*', '/']
]
def precedence_of(operator)
PRECEDENCES.find_index do |level_ops|
level_ops.include?(operator)
end
end
def lower_precedence(token, than:)
precedence_of(token) < precedence_of(than)
end
def apply(operator, l, r)
case operator
when '+'
l + r
when '-'
l - r
when '*'
l \* r
when '/'
l / r
else
raise Exception.new("Unknown operator #{operator}")
end
end
def collapse(operators, operands, next_operator: nil)
while !operators.empty? &&
(next_operator.nil? ||
lower_precedence(next_operator, than: operators.last))
r = operands.pop()
op = operators.pop()
l = operands.pop()
operands.push(apply(op, l, r))
end
end
def expect_operator(token)
if precedence_of(token).nil?
raise Exception.new("Expected operator, got #{token.inspect}")
end
return token
end
def expect_operand(token)
if token[/^\d+$/]
return token.to_i
end
raise Exception.new(
"Expected value or nested expression beginning with '(', instead got #{token.inspect}"
)
end
def should_cons(str, char)
return !str.nil? && str[/^\d+$/] && char[/^\d+$/]
end
loop do
input = gets
tokens = []
input.chars.each do |char|
if should_cons(tokens.last, char)
tokens.push(tokens.pop() + char)
else
if char.strip.size > 0
tokens.push(char)
end
end
end
puts tokens.inspect
expect_value = true
operators = []
operands = []
parentheses_stack = []
tokens.each do |token|
if expect_value
if token == '('
puts "PUSHING #{operators.inspect} #{operands.inspect}"
parentheses_stack << [operators, operands]
operators = []
operands = []
next
else
operand = expect_operand(token)
operands << operand
end
else
if token == ')'
puts "COLLAPSING #{operators.inspect} #{operands.inspect}"
collapse(operators, operands)
result = operands.last
puts "RESULT #{result.inspect}"
operators, operands = parentheses_stack.pop()
operands.push(result)
puts "POPPING(+ pushing) #{operators.inspect} #{operands.inspect}"
next
else
operator = expect_operator(token)
puts "COLLAPSING #{operators.inspect} #{operands.inspect}"
collapse(operators, operands, next_operator: operator)
operators.push(operator)
end
end
expect_value = !expect_value
end
collapse(operators, operands)
puts operands.last
end
- deleted 3y ago[deleted]