最近面试的时候，对方让我做了一道面试题，这里跟大家分享一下
题1:
给定一个三行的算式字符串，以字符串的形式返回算式的计算结果，计算符号只有加减乘除(+- */)，如果最终结果无法除尽，则以分数的形式返回。
image.png
结果为 :
5
-
(1.25也是正确答案) 4
例2:
image.png
结果:
4
- (1.3333不是正确答案，因为无法除尽) 3
package main
import (
"fmt"
"log"
"strconv"
)
//最大公约数
func gcd(a,b int) int{
if b== 0 {
return a
}
return gcd(b,a%b)
}
//最小公倍数
func lcm(a,b int ) int {
return a*b /gcd(a,b)
}
func main() {
//默认三行数据，字符串长度均一致，0，2排非分数位置以空格补齐
//默认包含一个运算符，以及两个数字
//排除以符号结尾的非正常表达式
str := []string{
" 2 1",
"2+-/2*-",
" 3 2",
}
f := action(str)
fmt.Printf("%d\n-\n%d",f.fenzi,f.fenmu)
}
//分数计算方法
func cal(opr string,a,b Fenshu) Fenshu{
switch opr {
case "+":
lcm_i := lcm(a.fenmu,b.fenmu)
return Fenshu{lcm_i/a.fenmu*a.fenzi+lcm_i/b.fenmu*b.fenzi,lcm_i}
case "-":
lcm_i := lcm(a.fenmu,b.fenmu)
return Fenshu{lcm_i/a.fenmu*a.fenzi-lcm_i/b.fenmu*b.fenzi,lcm_i}
case "*":
fenzi :=a.fenzi*b.fenzi
fenmu :=a.fenmu*b.fenmu
gcd_i := gcd(fenzi,fenmu)
return Fenshu{fenzi/gcd_i,fenmu/gcd_i}
case "/":
fenzi :=a.fenzi*b.fenmu
fenmu :=a.fenmu*b.fenzi
gcd_i := gcd(fenzi,fenmu)
return Fenshu{fenzi/gcd_i,fenmu/gcd_i}
default:
panic("err")
}
}
//比较优先级
func comp(opr string) int {
switch opr {
case "+","-":
return 1
case "*","/":
return 2
}
return 0
}
type Fenshu struct {
fenzi int //分子
fenmu int //分母
}
//定义两个栈 一个是分数栈 ，一个是操作符栈
var Fstack []Fenshu
var Ostack []string
func action(str []string) Fenshu {
//以第二行为循环标准
lens := len(str[1])
for i:=0;i<lens;i++ {
if isoperator(str[1][i:i+1]){
//如果第一排和第三排对应位置不为空则为分数
if str[0][i:i+1] !=" " && str[2][i:i+1] !=" "{
fenzi, _ := strconv.Atoi(str[0][i:i+1])
fenmu, _ := strconv.Atoi(str[2][i:i+1])
Fstack = append(Fstack,Fenshu{fenzi,fenmu})
log.Println(Ostack,Fstack)
if(len(Ostack)>1) {
popCal()
}
} else{
Ostack = append(Ostack,str[1][i:i+1])
}
}else{
fenzi, _ := strconv.Atoi(str[1][i:i+1])
Fstack = append(Fstack,Fenshu{fenzi,1})
log.Println(Ostack,Fstack)
if(len(Ostack)>1) {
popCal()
}
}
}
var res Fenshu
for len(Ostack)>0 && len(Fstack)>1 {
log.Println(Ostack,Fstack)
len_o := len(Ostack)
len_f := len(Fstack)
log.Println(len_o,len_f)
res = cal(Ostack[len_o-1],Fstack[len_f-2],Fstack[len_f-1])
Ostack = Ostack[:len_o-1]
Fstack[len_f-2] = res
Fstack = Fstack[:len_f-1]
}
return res
}
//判断是否优先计算
func popCal(){
len_o := len(Ostack)
len_f :=len(Fstack)
if len(Ostack)>1 {
if comp(Ostack[len_o-1]) > comp(Ostack[len_o-2]){
res := cal(Ostack[len_o-1],Fstack[len_f-2],Fstack[len_f-1])
Ostack = Ostack[:len_o-1]
Fstack = Fstack[:len_f-2]
Fstack =append(Fstack,res)
}
}
}
func isoperator(str string) bool{
switch str {
case "-","+","*","/":
return true
}
return false
}
首先我们需要解决几个关键点
- 如何处理字符串
2.如何进行分数运算
- 如何解决运算先后顺序问题
下面说下我的解决思路
如何处理字符串
- 字符串分为三行 ，那么我们使用中间这一行作为循环的基础，因为中间这一行是完整的不会包含空格等问题
2.在处理过程中，我使用了一个结构体记录分数的分子和分母，以便进行后续计算。 - 当碰到数字时，我们将数字转化成 （数字/1）的形式记录在分数的栈里，如果是“-“ 号的时候判断是否在其上方和下方有数字，如果有说明是个分数，如果没有记录到符号的栈里
如何进行分数运算
- 分数运算其实很简单 ，利用小学的内容即可
1.1分数乘法， 分子A分子B / 分母A 分母 B 结果同时除以 分子和分母的最大公约数 （也就是约分） 1/2 * 2/3 = 2/6 = 1/3
1.2分数除法 ， 分子A分母B / 分母A 分子 B
1.3 分数加法 求 最大公倍数（分母A ， 分母B） 分子A （最大公倍数/分母A ） + 分子B （最大公倍数/分母B ) / 最大公倍数
举例来说就是 2/3 + 4/5 = （10 - 12）/15
1.4 分数减法同理 不展示了
如何解决运算先后顺序问题
- 这里使用两个栈解决，一个栈是数字栈，一个是符号栈
- 数字栈增加数字时， 对符号栈进行弹栈操作，同时弹出最后两个符号，比较优先级，（这里提前设置优先级，/ 为1 ；+-为0） 如果高优先级则计算后两个数的值，并重新入栈
注意：当时写的时候脑子不好使，这里可以改成，如果碰到 / 直接计算。使符号栈里第一次结果只有 + - 再二次循环就行了 - 至此就解决了所有问题
