3
\$\begingroup\$

This is a solution to this problem: https://www.codewars.com/kata/53005a7b26d12be55c000243/train/ruby

The task is to make a simple interpreter that will take expressions and calculate the results. I'm just looking for general feedback on following Ruby standard practices and ways I could shorten the code by omitting parentheses for example:

class Interpreter

  def input expr
    if expr.strip == ""
      return ""
    end
    # puts expr
    tokens = tokenize(expr).map{ |a| a[0] }    
    parsedTokens = parseTokens tokens
    if parsedTokens.length == 1
      if !@variables.key? parsedTokens[0].name
        raise 'unitialized variable'
      end
      return @variables[parsedTokens[0].name]
    end
    # todo can the user enter just a number?
    leastPrecedentNode = partition parsedTokens
    rootOfBuiltTree = buildTree leastPrecedentNode
    result = calculateRecursive rootOfBuiltTree
    result
  end

  private

  class OperatorInfo
      @@operators = { '=' => 0, '+' => 1, '-' => 1, '*' => 2, '/' => 2, '%' => 2 }
      @@assignmentOperator = '='

      def self.operators
        @@operators
      end

      def self.assignmentOperator
        @@assignmentOperator
      end
  end

  class ParseUnit
    attr_reader :overallIndex
    attr_reader :nestLevel
    attr_reader :indexInLevel

    def initialize(overallIndex, nestLevelArg, indexInLevelArg)
      @overallIndex = overallIndex
      @nestLevel = nestLevelArg
      @indexInLevel = indexInLevelArg
    end
  end

  class ConstantParse < ParseUnit
    attr_reader :value

    def initialize(value, overallIndex, nestLevel, indexInLevel)
      super(overallIndex, nestLevel, indexInLevel)
      @value = value
    end
  end

  class OperatorParse < ParseUnit
    attr_reader :operator
    attr_reader :priority

    def initialize(operator, overallIndex, nestLevel, indexInLevel)
      super(overallIndex, nestLevel, indexInLevel)
      @operator = operator
      @priority = OperatorInfo.operators[operator]
    end
  end

  class VariableParse < ParseUnit
    attr_reader :name

    def initialize(name, overallIndex, nestLevel, indexInLevel)
      super(overallIndex, nestLevel, indexInLevel)
      @name = name
    end
  end

  def parseTokens (tokens)
    ret = []
    nestLevel = 0
    indexes = [0]
    overallIndex = 0
    tokens.each do | t | 
      # can be operator, constant number, paren, variable 
      # puts "curToken is #{t}"

      case t       
      #operator
      when OperatorInfo.operators.keys.include?(t).to_s == 'true' ? t : ''
        ret.push OperatorParse.new t, overallIndex, nestLevel, indexes[nestLevel]
          overallIndex += 1
          indexes[nestLevel] += 1 
      # is a constant number
      when /\A\d+\z/        
        ret.push ConstantParse.new t.to_i, overallIndex, nestLevel, indexes[nestLevel]
        overallIndex += 1
        indexes[nestLevel] += 1
      when '('
        nestLevel += 1
        if indexes.length <= nestLevel
          indexes.push(0)
        end
      when ')'
        nestLevel -= 1
      #variable
      when String
        ret.push VariableParse.new t, overallIndex, nestLevel, indexes[nestLevel]
        overallIndex += 1
        indexes[nestLevel] += 1
      else
        puts "error in parse tokens with token #{t}"
      end
    end
    ret
  end

  class OperatorNode
    attr_reader :operator
    attr_reader :left
    attr_reader :right

    def initialize(operator, left, right)
      @left = left
      @right = right
      @operator = operator
      @priority = OperatorInfo.operators[operator] 
    end
  end

  def partition(parsedTokens)
    opTokens = parsedTokens.select { |token| token.is_a?(OperatorParse) }
    op = leastPrecedentOp opTokens
    left = parsedTokens.select { |x| x.overallIndex < op.overallIndex }
    right = parsedTokens.select { |x| x.overallIndex > op.overallIndex }
    OperatorNode.new op, left, right
  end

  def leastPrecedentOp opTokens
    if opTokens.length == 1 
      return opTokens[0]
    end
    # todo dry out this sort with the next one
    sortedByNestLevel = opTokens.sort_by { |x| x.nestLevel }
    nestLevelTies = sortedByNestLevel.select { |x| x.nestLevel == sortedByNestLevel[0].nestLevel }
    if nestLevelTies.length == 1
      return nestLevelTies[0]
    end
    sortedByPriority = nestLevelTies.sort_by { |x| x.priority }
    priorityTies = sortedByPriority.select { |x| x.priority == sortedByPriority[0].priority }
    if priorityTies.length == 1
      return priorityTies[0]
    end
    sortedByIndexInLevel = priorityTies.sort_by { |x| x.indexInLevel * -1 }
    sortedByIndexInLevel[0]
  end

  def buildTree(opNode)
    # puts opNode
    # base case
    leftIsSingle = opNode.left.length == 1
    rightIsSingle = opNode.right.length == 1
    if leftIsSingle && rightIsSingle
      return OperatorNode.new opNode.operator.operator, opNode.left, opNode.right   
    end
    # recursive call
    leftRet = nil
    if leftIsSingle
      leftRet = opNode.left[0]
    else
      leftPart = partition opNode.left
      leftRet = buildTree leftPart
    end

    rightRet = nil
    if rightIsSingle
      rightRet = opNode.right[0]
    else
      rightPart = partition opNode.right
      rightRet = buildTree rightPart
    end

    # combine and return
    OperatorNode.new opNode.operator.operator, leftRet, rightRet
  end

  def calculateRecursive node
    # base case
    if isLeaf? node, nil
      return getValue node
    end    
    leftIsLeaf = isLeaf? node, node.left
    rightIsLeaf = isLeaf? node, node.right
    if leftIsLeaf && rightIsLeaf
      if node.operator == OperatorInfo.assignmentOperator
        return calculateImpl node.operator, node.left[0].name, (getValue node.right)
      end
      leftVal = getValue node.left
      rightVal = getValue node.right
      return calculateImpl node.operator, leftVal, rightVal
    end
    # recursive call
    leftResult = nil
    if leftIsLeaf && node.operator != OperatorInfo.assignmentOperator
      leftResult = getValue node.left
    elsif leftIsLeaf && node.operator
      leftResult = node.left.name
    else
      leftResult = calculateRecursive node.left
    end
    rightResult = nil
    if rightIsLeaf
      rightResult = getValue node.right
    else
      rightResult = calculateRecursive node.right
    end
    # combine and return
    result = calculateImpl node.operator, leftResult, rightResult
    result
  end

  def isLeaf?(parent, node)
    # if parent
    isConstant = node.is_a? ConstantParse 
    if node.is_a? Array 
      isConstant = node[0].is_a? ConstantParse
    end
    isVariable = node.is_a? VariableParse
    if node.is_a? Array 
      isVariable = node[0].is_a? VariableParse
    end
    return isConstant || isVariable
  end

  def getValue node
    nodeVal = nil
    if node.is_a? Array
      nodeVal = node[0]
    else
      nodeVal = node
    end
    if nodeVal.is_a? ConstantParse
      return nodeVal.value
    end
    if nodeVal.is_a? VariableParse
      if @variables.key? nodeVal.name
        return @variables[nodeVal.name]
      end
      return nodeVal.name
    end
  end

  def calculateImpl(operator, left, right)
    #puts "#{left} #{operator} #{right}"
    case operator
    when '+'
      return left + right
    when '-'
      return left - right
    when '/'
      return left.to_f / right
    when '*'
      return left * right
    when '%'
      return left % right
    when '='
      @variables[left] = right
      return right
    end
  end

  def initialize
    @variables = {}
  end  

  def tokenize program
    return [] if program == ''
    regex = /\s*([-+*\/\%=\(\)]|[A-Za-z_][A-Za-z0-9_]*|[0-9]*\.?[0-9]+)\s*/
    program.scan(regex).select { |s| !(s =~ /^\s*$/) }
  end
end
\$\endgroup\$
3
+200
\$\begingroup\$

What you mentioned about removing parentheses like you did in def input expr method definition, in general is a bad practice. My suggestions:

  • Start running rubocop -a your_path/file.rb to auto-correct most of style problems in your code.
  • Fix manually variable names like parsedTokens or method names like parseTokens to be snake cased.
  • Most of the time, there are no good reasons to use class variables like you did in @@operators. Actually, I'd move those vars. out of OperatorInfo and remove that class definition, then defining them as constants in the main class as:
class Interpreter
  # .freeze is to really define these variables as constants (immutables)
  OPERATORS = { '=' => 0, '+' => 1, '-' => 1, '*' => 2, '/' => 2, '%' => 2 }.freeze
  ASSIGNMENT_OPERATOR = '='.freeze
  • You can define readers in a single call, like:
  class ParseUnit
    attr_reader :overall_index, :nest_level, :index_in_level
  • If possible, define sub classes like OperatorNode in separate files. If not, defining them under private isn't really effective:
class Interpreter
  def self.calling_inner_class
    OperatorNode
  end

  private
  class OperatorNode
    # ...
  end
end

Interpreter.calling_inner_class # Interpreter::OperatorNode
# This shouldn't work for private classes
Interpreter::OperatorNode # => Interpreter::OperatorNode

An option to make them really private is adding private_constant to every class definition like:

class Interpreter
  def self.calling_inner_class
    # This operates normally
    OperatorNode
  end

  class OperatorNode
    # ...
  end
  private_constant :OperatorNode
end

Interpreter.calling_inner_class # Interpreter::OperatorNode
# Throwing an error, which is correct
Interpreter::OperatorNode # NameError: private constant Interpreter::OperatorNode referenced
\$\endgroup\$
2
  • \$\begingroup\$ Thanks a lot for the feedback! I appreciate it! \$\endgroup\$ May 27 '20 at 0:30
  • 2
    \$\begingroup\$ @reggaeguitar after looking again my answer, I realised the last part wasn't correct at all, so I removed everything related with private classes within self blocks as it's not really defining the classes as privates. Cheers \$\endgroup\$ May 27 '20 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.