最近面試的時(shí)候，對(duì)方讓我做了一道面試題，這里跟大家分享一下
題1:
給定一個(gè)三行的算式字符串，以字符串的形式返回算式的計(jì)算結(jié)果，計(jì)算符號(hào)只有加減乘除(+- */)，如果最終結(jié)果無(wú)法除盡，則以分?jǐn)?shù)的形式返回。
image.png
結(jié)果為 :
5
-
(1.25也是正確答案) 4
例2:
image.png
結(jié)果:
4
- (1.3333不是正確答案，因?yàn)闊o(wú)法除盡) 3
package main
import (
"fmt"
"log"
"strconv"
)
//最大公約數(shù)
func gcd(a,b int) int{
if b== 0 {
return a
}
return gcd(b,a%b)
}
//最小公倍數(shù)
func lcm(a,b int ) int {
return a*b /gcd(a,b)
}
func main() {
//默認(rèn)三行數(shù)據(jù)，字符串長(zhǎng)度均一致，0，2排非分?jǐn)?shù)位置以空格補(bǔ)齊
//默認(rèn)包含一個(gè)運(yùn)算符，以及兩個(gè)數(shù)字
//排除以符號(hào)結(jié)尾的非正常表達(dá)式
str := []string{
" 2 1",
"2+-/2*-",
" 3 2",
}
f := action(str)
fmt.Printf("%d\n-\n%d",f.fenzi,f.fenmu)
}
//分?jǐn)?shù)計(jì)算方法
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")
}
}
//比較優(yōu)先級(jí)
func comp(opr string) int {
switch opr {
case "+","-":
return 1
case "*","/":
return 2
}
return 0
}
type Fenshu struct {
fenzi int //分子
fenmu int //分母
}
//定義兩個(gè)棧 一個(gè)是分?jǐn)?shù)棧 ，一個(gè)是操作符棧
var Fstack []Fenshu
var Ostack []string
func action(str []string) Fenshu {
//以第二行為循環(huán)標(biāo)準(zhǔn)
lens := len(str[1])
for i:=0;i<lens;i++ {
if isoperator(str[1][i:i+1]){
//如果第一排和第三排對(duì)應(yīng)位置不為空則為分?jǐn)?shù)
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
}
//判斷是否優(yōu)先計(jì)算
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
}
首先我們需要解決幾個(gè)關(guān)鍵點(diǎn)
- 如何處理字符串
2.如何進(jìn)行分?jǐn)?shù)運(yùn)算
- 如何解決運(yùn)算先后順序問(wèn)題
下面說(shuō)下我的解決思路
如何處理字符串
- 字符串分為三行 ，那么我們使用中間這一行作為循環(huán)的基礎(chǔ)，因?yàn)橹虚g這一行是完整的不會(huì)包含空格等問(wèn)題
2.在處理過(guò)程中，我使用了一個(gè)結(jié)構(gòu)體記錄分?jǐn)?shù)的分子和分母，以便進(jìn)行后續(xù)計(jì)算。 - 當(dāng)碰到數(shù)字時(shí)，我們將數(shù)字轉(zhuǎn)化成 （數(shù)字/1）的形式記錄在分?jǐn)?shù)的棧里，如果是“-“ 號(hào)的時(shí)候判斷是否在其上方和下方有數(shù)字，如果有說(shuō)明是個(gè)分?jǐn)?shù)，如果沒(méi)有記錄到符號(hào)的棧里
如何進(jìn)行分?jǐn)?shù)運(yùn)算
- 分?jǐn)?shù)運(yùn)算其實(shí)很簡(jiǎn)單 ，利用小學(xué)的內(nèi)容即可
1.1分?jǐn)?shù)乘法， 分子A分子B / 分母A 分母 B 結(jié)果同時(shí)除以 分子和分母的最大公約數(shù) （也就是約分） 1/2 * 2/3 = 2/6 = 1/3
1.2分?jǐn)?shù)除法 ， 分子A分母B / 分母A 分子 B
1.3 分?jǐn)?shù)加法 求 最大公倍數(shù)（分母A ， 分母B） 分子A （最大公倍數(shù)/分母A ） + 分子B （最大公倍數(shù)/分母B ) / 最大公倍數(shù)
舉例來(lái)說(shuō)就是 2/3 + 4/5 = （10 - 12）/15
1.4 分?jǐn)?shù)減法同理 不展示了
如何解決運(yùn)算先后順序問(wèn)題
- 這里使用兩個(gè)棧解決，一個(gè)棧是數(shù)字棧，一個(gè)是符號(hào)棧
- 數(shù)字棧增加數(shù)字時(shí)， 對(duì)符號(hào)棧進(jìn)行彈棧操作，同時(shí)彈出最后兩個(gè)符號(hào)，比較優(yōu)先級(jí)，（這里提前設(shè)置優(yōu)先級(jí)，/ 為1 ；+-為0） 如果高優(yōu)先級(jí)則計(jì)算后兩個(gè)數(shù)的值，并重新入棧
注意：當(dāng)時(shí)寫(xiě)的時(shí)候腦子不好使，這里可以改成，如果碰到 / 直接計(jì)算。使符號(hào)棧里第一次結(jié)果只有 + - 再二次循環(huán)就行了 - 至此就解決了所有問(wèn)題
