• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode770.基本计算器IV|BasicCalculatorIV

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址: https://www.cnblogs.com/strengthen/p/10536324.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {"e": 1} (given in terms of evalvars = ["e"] and evalints = [1]), return a list of tokens representing the simplified expression, such as ["-1*a","14"]

  • An expression alternates chunks and symbols, with a space separating each chunk and symbol.
  • A chunk is either an expression in parentheses, a variable, or a non-negative integer.
  • A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like "2x" or "-x".

Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction. For example, expression = "1 + 2 * 3" has an answer of ["7"].

The format of the output is as follows:

  • For each term of free variables with non-zero coefficient, we write the free variables within a term in sorted order lexicographically. For example, we would never write a term like "b*a*c", only "a*b*c".
  • Terms have degree equal to the number of free variables being multiplied, counting multiplicity. (For example, "a*a*b*c" has degree 4.) We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
  • The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.)  A leading coefficient of 1 is still printed.
  • An example of a well formatted answer is ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"] 
  • Terms (including constant terms) with coefficient 0 are not included.  For example, an expression of "0" has an output of [].

Examples:

Input: expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
Output: ["-1*a","14"]

Input: expression = "e - 8 + temperature - pressure",
evalvars = ["e", "temperature"], evalints = [1, 12]
Output: ["-1*pressure","5"]

Input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
Output: ["1*e*e","-64"]

Input: expression = "7 - 7", evalvars = [], evalints = []
Output: []

Input: expression = "a * b * c + b * a * c * 4", evalvars = [], evalints = []
Output: ["5*a*b*c"]

Input: expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))",
evalvars = [], evalints = []
Output: ["-1*a*a*b*b","2*a*a*b*c","-1*a*a*c*c","1*a*b*b*b","-1*a*b*b*c","-1*a*b*c*c","1*a*c*c*c","-1*b*b*b*c","2*b*b*c*c","-1*b*c*c*c","2*a*a*b","-2*a*a*c","-2*a*b*b","2*a*c*c","1*b*b*b","-1*b*b*c","1*b*c*c","-1*c*c*c","-1*a*a","1*a*b","1*a*c","-1*b*c"]

Note:

  1. expression will have length in range [1, 250].
  2. evalvars, evalints will have equal lengths in range [0, 100].

给定一个表达式 expression 如 expression = "e + 8 - a + 5" 和一个求值映射,如 {"e": 1}(给定的形式为 evalvars = ["e"] 和 evalints = [1]),返回表示简化表达式的标记列表,例如 ["-1*a","14"]

  • 表达式交替使用块和符号,每个块和符号之间有一个空格。
  • 块要么是括号中的表达式,要么是变量,要么是非负整数。
  • 块是括号中的表达式,变量或非负整数。
  • 变量是一个由小写字母组成的字符串(不包括数字)。请注意,变量可以是多个字母,并注意变量从不具有像 "2x" 或 "-x" 这样的前导系数或一元运算符 。

表达式按通常顺序进行求值:先是括号,然后求乘法,再计算加法和减法。例如,expression = "1 + 2 * 3" 的答案是 ["7"]

输出格式如下:

  • 对于系数非零的每个自变量项,我们按字典排序的顺序将自变量写在一个项中。例如,我们永远不会写像 “b*a*c” 这样的项,只写 “a*b*c”
  • 项的次数等于被乘的自变量的数目,并计算重复项。(例如,"a*a*b*c" 的次数为 4。)。我们先写出答案的最大次数项,用字典顺序打破关系,此时忽略词的前导系数。
  • 项的前导系数直接放在左边,用星号将它与变量分隔开(如果存在的话)。前导系数 1 仍然要打印出来。
  • 格式良好的一个示例答案是 ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"] 。
  • 系数为 0 的项(包括常数项)不包括在内。例如,“0” 的表达式输出为 []。

示例:

输入:expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
输出:["-1*a","14"]

输入:expression = "e - 8 + temperature - pressure",
evalvars = ["e", "temperature"], evalints = [1, 12]
输出:["-1*pressure","5"]

输入:expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
输出:["1*e*e","-64"]

输入:expression = "7 - 7", evalvars = [], evalints = []
输出:[]

输入:expression = "a * b * c + b * a * c * 4", evalvars = [], evalints = []
输出:["5*a*b*c"]

输入:expression = "((a - b) * (b - c) + (c - a)) * ((a - b) + (b - c) * (c - a))",
evalvars = [], evalints = []
输出:["-1*a*a*b*b","2*a*a*b*c","-1*a*a*c*c","1*a*b*b*b","-1*a*b*b*c","-1*a*b*c*c","1*a*c*c*c","-1*b*b*b*c","2*b*b*c*c","-1*b*c*c*c","2*a*a*b","-2*a*a*c","-2*a*b*b","2*a*c*c","1*b*b*b","-1*b*b*c","1*b*c*c","-1*c*c*c","-1*a*a","1*a*b","1*a*c","-1*b*c"]

提示:

  1. expression 的长度在 [1, 250] 范围内。
  2. evalvars, evalints 在范围 [0, 100] 内,且长度相同。

同样的测试用例。
使用【测试用例】单独执行,执行正确。
input
"(e + 8) * (e - 8)"
[]
[]
 
Output
["1*e*e","-64"]
 
Expected
["1*e*e","-64"]
但是提交时,提示解答错误。问题不大。
Input
"(e + 8) * (e - 8)"
[]
[]
 
Output
["-63"]
 
Expected
["1*e*e","-64"]
  1 class Solution {
  2     //evaluation map
  3     static var map:[String:Int] = [String:Int]()   
  4     
  5     func basicCalculatorIV(_ expression: String, _ evalvars: [String], _ evalints: [Int]) -> [String] {
  6         for i in 0..<evalvars.count
  7         {
  8             Solution.map[evalvars[i]] = evalints[i]            
  9         }
 10         var i:Int = 0
 11         var l:Int = expression.count
 12         var stack:[Expression] = [Expression]()
 13         var priStack:[Int] = [Int]()
 14         var zero:Expression = Expression(0)
 15         stack.append(zero)
 16         priStack.append(0)
 17         var pri:Int = 0
 18         
 19         while (i < l)
 20         {
 21             var ch:Character = expression[i]
 22             if ch.isDigit()
 23             {
 24                 var num:Int = 0
 25                 while (i < l && expression[i].isDigit())
 26                 {
 27                     num = num * 10 + (expression[i].ascii - 48)
 28                     i += 1
 29                 }
 30                 stack.append(Expression(num))
 31                 continue
 32             }
 33             if ch.isLetter()
 34             {
 35                 var s:String = String()
 36                 while (i < l && expression[i].isLetter())
 37                 {
 38                     s.append(expression[i])
 39                     i += 1             
 40                 }
 41                 stack.append(Expression(s))
 42                 continue
 43             }
 44             if ch == "(" {pri += 2}
 45             if ch == ")" {pri -= 2}
 46             if ch == "+" || ch == "-" || ch == "*"
 47             {
 48                 var nowPri:Int = pri
 49                 if ch == "*" {nowPri += 1}
 50                 while (!priStack.isEmpty && nowPri <= priStack.last!)
 51                 {
 52                     var now:Expression = stack.removeLast()
 53                     var last:Expression = stack.removeLast()
 54                     priStack.removeLast()
 55                     stack.append(last.cal(now))      
 56                 }
 57                 stack[stack.count - 1].oper = ch
 58                 priStack.append(nowPri)           
 59             }   
 60             i += 1   
 61         }
 62         
 63         while (stack.count > 1)
 64         {
 65             var now:Expression = stack.removeLast()
 66             var last:Expression = stack.removeLast()
 67             stack.append(last.cal(now)) 
 68         }
 69         
 70         return stack.last!.toList()
 71     }
 72 }
 73 
 74 class Term
 75 {
 76     //the parameter of this term
 77     var para:Int = 1
 78     //each factor (e.a. a*b*b*c->{a,b,b,c})    
 79     var arr:[String] = [String]()       
 80     
 81     init(_ x:Int)
 82     {
 83         self.para = x
 84     }
 85     
 86     init(_ s:String)
 87     {
 88         if Solution.map[s] == nil
 89         {
 90             arr.append(s)
 91         }
 92         else
 93         {
 94             para = Solution.map[s]!
 95         }
 96     }
 97     
 98     init(_ that:Term)
 99     {
100         self.para = that.para
101         self.arr = that.arr     
102     }
103     
104     func toString() -> String
105     {
106         if para == 0 {return String()}
107         var ans:String = String()
108         for s in arr
109         {
110             ans += ("*" + s)
111         }
112         return String(para) + ans
113     }  
114     
115     func equals(_ that:Term) -> Bool
116     {
117         if self.arr.count != that.arr.count
118         {
119             return false
120         }
121         for i in 0..<self.arr.count
122         {
123             if self.arr[i] != that.arr[i]
124             {
125                 return false
126             }
127         }
128         return true
129     }
130     
131     func compareTo(_ that:Term) -> Int
132     {
133         if self.arr.count > that.arr.count {return -1}
134         if self.arr.count < that.arr.count {return 1}
135         for i in 0..<self.arr.count
136         {
137             var x:Int = 0
138             if self.arr[i] > that.arr[i]
139             {
140                 x = 1
141             }
142             else if self.arr[i] < that.arr[i]
143             {
144                 x = -1
145             }
146             else
147             {
148                 x = 0                
149             }
150             if x != 0 {return x}
151         }
152         return 0
153     }
154     
155     func times(_ that:Term) -> Term
156     {
157         var pro = Term(self.para * that.para)
158         for s in self.arr 
159         {
160             pro.arr.append(String(s))
161         }
162         for s in that.arr
163         {
164             pro.arr.append(String(s))
165         }
166         pro.arr = pro.arr.sorted(by:>)
167         return pro
168     }
169 }
170 
171 class Expression
172 {  
173     //Term List
174     var list:[Term] = [Term]()
175     var oper:Character = "+"   
176     
177     init(_ x:Int)
178     {
179         self.list.append(Term(x))
180     }
181     
182     init(_ s:String)
183     {
184         self.list.append(Term(s))
185     } 
186     
187     init(_ l:[Term])
188     {
189         self.list = l   
190     } 
191     
192     func times(_ that:Expression) -> Expression
193     {
194         var c:[Term] = [Term]()
195         for t1 in self.list
196         {
197             for t2 in that.list
198             {
199                 c.append(t1.times(t2))
200             }
201         }
202         c = combine(c)
203         return Expression(c)
204     }
205     
206     func plus(_ that:Expression,_ sgn:Int) -> Expression
207     {
208         var c:[Term] = [Term]()
209         for t in self.list
210         {
211             c.append(Term(t))
212         }
213         for t in that.list
214         {
215             var t2:Term = Term(t)
216             t2.para = t2.para * sgn
217             c.append(t2)                
218         }
219         c = combine(c)
220         return Expression(c)
221     }
222     
223     func cal(_ that:Expression) -> Expression
224     {
225         if oper == "+"
226         {               
227             return plus(that,1)
228         }
229         if oper == "-"
230         {
231             return plus(that,-1)
232         }
233         return times(that)
234     }
235     
236     func toList() -> [String]
237     {
238         var ans:[String] = [String]()
239         for t in list
240         {
241             var s:String = t.toString()
242             if s.count > 0 {ans.append(s)}
243         }
244         return ans
245     }
246     
247     func combine(_ a:[Term]) -> [Term]
248     {
249         var a = a
250         a.sort(by:{(t1:Term,t2:Term) -> Bool in
251                    return t1.compareTo(t2) < 0})
252         var c:[Term] = [Term]()
253         for t in a
254         {
255             if c.count != 0 && t.equals(c.last!)
256             {
257                 c[c.count - 1].para += t.para
258             }
259             else
260             {
261                 c.append(Term(t));
262             }
263         }
264         return c
265     }
266 }
267 
268 //String扩展
269 extension String {        
270     //subscript函数可以检索数组中的值
271     //直接按照索引方式截取指定索引的字符
272     subscript (_ i: Int) -> Character {
273         //读取字符
274         get {return self[index(startIndex, offsetBy: i)]}
275     }
276 }
277 
278 //Character扩展 
279 extension Character  
280 {  
281   //Character转ASCII整数值(定义小写为整数值)
282    var ascii: Int {
283        get {
284            return Int(self.unicodeScalars.first?.value ?? 0)
285        }       
286     }    
287     
288     func isDigit() -> Bool
289     {
290         if self.ascii > 47 && self.ascii < 58
291         {
292             return true            
293         }
294         return false
295     }
296     
297     func isLetter() -> Bool
298     {
299         if (self.ascii > 64 && self.ascii < 91) || self.ascii > 96 && self.ascii < 123
300         {
301             return true            
302         }
303         return false
304     }
305 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode710.黑名单中的随机数|RandomPickwithBlacklist发布时间:2022-07-13
下一篇:
swift学习-计时器发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap