【算法】String Calculation

Given a string like “a + b”, return the value of the string with the regulation we defined.

For Exmaple:

“a + b” => “ab”
“abc - 1” => “ab”
“a^3” => “aaa”
“(a + b)^3” => “ababab”

class EquationParser
  PRECEDENCE = [
    ['(', ')'],
    ['+', '-'],
    ['^']
  ]

  REG_VARIABLE = /(\d|[a-z])+/
  REG_OPERATOR = /[\+\-\^]/
  REG_PARENTHESIS = /[\(\)]/
  REG_SPACE = /\s+/

  class << self
    def exec(equation)
      exec_postfix parse_to_postfix(equation)
    end

    # parse infix equation to postfix
    def parse_to_postfix(equation)
      postfix_equation, stack = [], []
      until equation.nil? or equation.size == 0
        case equation
        when /^(#{REG_VARIABLE})/ # string and number
          token = $1
          postfix_equation << token
        when /^(#{REG_OPERATOR})/ # operator
          token = $1
          if stack.empty?
            stack << token
          else
            while stack.size > 0 && precedence(token) <= precedence(stack.last)
              postfix_equation << stack.pop
            end
            stack << token
          end
        when /^(#{REG_PARENTHESIS})/ # parenthesis
          token = $1
          case token
          when '('
            stack << token
          when ')'
            postfix_equation << stack.pop while !stack.empty? && stack.last != '('
            raise "mismatched parenthesis '#{token}'" if stack.last != '('
            stack.pop
          else
            raise "parenthesis '#{token}' wrong"
          end
        else
          raise "unknown token! expression is '#{equation}'"
        end
        equation = equation[token.size..-1]
      end

      until stack.empty?
        raise "mismatched parenthesis '('" if stack.last == '('
        postfix_equation << stack.pop
      end
      postfix_equation
    end

    def exec_postfix(postfix_equation)
      stack = []
      postfix_equation.each do |token|
        case token
        when REG_VARIABLE
          stack << token
        when REG_OPERATOR
          raise 'stack size < 2' if stack.size < 2
          param2, param1 = stack.pop, stack.pop
          stack << exec_equation(param1, token, param2)
        end
      end
      raise 'final stack size must be 1' if stack.size != 1
      stack.first
    end

    def precedence(operator)
      result = PRECEDENCE.index { |group| group.include?(operator) }
      raise "unknown operator '#{op}'" if result.nil?
      result
    end

    def exec_equation(param1, operator, param2)
      case operator
      when '+'
        return param1 + param2
      when '-'
        return param1[0, param1.size - param2.to_i] || ''
      when '^'
        return param1 * param2.to_i
      else
        raise "operator '#{operator}' wrong"
      end
    end
  end
end

print("#{EquationParser.exec gets.chomp}\n")