【算法】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”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
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")
Yunjie Zhang wechat
扫一扫上面的二维码加我微信