实现流程：
①把input输入的字符串进行拆分，变成一个一个单词，要设计词法分析器，大部分都设计相关的词法分析器。parser。它会不断读取每一个字符，然后生成对应的一个个词元。
我们将词元和词法分析器，分别用两个结构体表示出来。
type Token struct { Type string //对应我们上面的词元类型 Literal string // 实际的string字符 } type Lexer struct { input string // 输入 position int // 当前位置 readPosition int // 将要读取的位置 ch byte //当前字符 }
词法分析器操作：
- 不断读取字符串的每一个字符，更新结构体的值。
- 要注意考虑跳过空白字符/制表符。
- 对于数字要单独考虑，因为 ’567‘ 这是一个词元。
②构建语法树，要让计算机按照你想要的方式进行计算。遵循数学里面的计算法则。之前数据结构中学习二叉树时，都知道中缀表达式，对应了我们的计算规则。当然前缀/后缀也可以计算出正确的值，比如逆波兰式求职，这里不在赘述。可以看另一篇博客有通过后缀表达式计算值，安置传送门。
③考虑两种计算情况。
情况一：++i；某个操作符作为前缀与后面数字发生反应。同样还包括我们的-1。
情况二：1 + 2。操作符在中间。
// package calc package main import ( "bufio" "bytes" "fmt" "os" "strconv" ) const ( ILLEGAL = "ILLEGAL" EOF = "EOF" INT = "INT" PLUS = "+" MINUS = "-" ASTERISK = "*" SLASH = "/" LPAREN = "(" RPAREN = ")" ) const ( _ int = iota LOWEST SUM // +, - PRODUCT // *, / PREFIX // -X CALL // (X) ) var precedences = map[string]int{ PLUS: SUM, MINUS: SUM, SLASH: PRODUCT, ASTERISK: PRODUCT, LPAREN: CALL, } func Calc(input string) int64 { lexer := NewLex(input) parser := NewParser(lexer) exp := parser.ParseExpression(LOWEST) return Eval(exp) } func main() { reader := bufio.NewReader(os.Stdin) n, err := reader.ReadString('\n') if err != nil { fmt.Println("error") } //fmt.Println(n) fmt.Println(Calc(n)) } func Eval(exp Expression) int64 { switch node := exp.(type) { case *IntegerLiteralExpression: return node.Value case *PrefixExpression: rightV := Eval(node.Right) return evalPrefixExpression(node.Operator, rightV) case *InfixExpression: leftV := Eval(node.Left) rightV := Eval(node.Right) return evalInfixExpression(leftV, node.Operator, rightV) } return 0 } func evalPrefixExpression(operator string, right int64) int64 { if operator != "-" { return 0 } return -right } func evalInfixExpression(left int64, operator string, right int64) int64 { switch operator { case "+": return left + right case "-": return left - right case "*": return left * right case "/": if right != 0 { return left / right } else { return 0 } default: return 0 } } type Token struct { Type string Literal string } func newToken(tokenType string, c byte) Token { return Token{ Type: tokenType, Literal: string(c), } } type Lexer struct { input string position int readPosition int ch byte } func NewLex(input string) *Lexer { l := &Lexer{input: input} l.readChar() return l } func (l *Lexer) NextToken() Token { var tok Token l.skipWhitespace() //跳过全部空白字符或制表符 switch l.ch { case '(': tok = newToken(LPAREN, l.ch) case ')': tok = newToken(RPAREN, l.ch) case '+': tok = newToken(PLUS, l.ch) case '-': tok = newToken(MINUS, l.ch) case '/': tok = newToken(SLASH, l.ch) case '*': tok = newToken(ASTERISK, l.ch) case 0: //对于超出字符串范围的进行结束 EOF tok.Literal = "" tok.Type = EOF default: if isDigit(l.ch) { tok.Type = INT tok.Literal = l.readNumber() return tok } else { tok = newToken(ILLEGAL, l.ch) //非法字符处理 } } l.readChar() return tok } func isDigit(ch byte) bool { return '0' <= ch && ch <= '9' } // 读一个字符，超出输入的字符串范围，就将当前字符置为0，结束读取 func (l *Lexer) readChar() { if l.readPosition >= len(l.input) { l.ch = 0 } else { l.ch = l.input[l.readPosition] } l.position = l.readPosition l.readPosition += 1 } // 读取数字的单独函数 因为345这是一个数 func (l *Lexer) readNumber() string { position := l.position for isDigit(l.ch) { l.readChar() } return l.input[position:l.position] //返回一个数据 } // 知道是这些制表符就再往下读一个 func (l *Lexer) skipWhitespace() { for l.ch == ' ' || l.ch == '\t' || l.ch == '\n' || l.ch == '\r' { l.readChar() } } // ast type Expression interface { String() string } type IntegerLiteralExpression struct { Token Token Value int64 } func (il *IntegerLiteralExpression) String() string { return il.Token.Literal } type PrefixExpression struct { Token Token Operator string Right Expression } func (pe *PrefixExpression) String() string { var out bytes.Buffer out.WriteString("(") out.WriteString(pe.Operator) out.WriteString(pe.Right.String()) out.WriteString(")") return out.String() } type InfixExpression struct { Token Token Left Expression Operator string Right Expression } func (ie *InfixExpression) String() string { var out bytes.Buffer out.WriteString("(") out.WriteString(ie.Left.String()) out.WriteString(" ") out.WriteString(ie.Operator) out.WriteString(" ") out.WriteString(ie.Right.String()) out.WriteString(")") return out.String() } // parser type ( prefixParseFn func() Expression //函数 返回参数是Expression接口 infixParseFn func(Expression) Expression ) type Parser struct { l *Lexer curToken Token peekToken Token prefixParseFns map[string]prefixParseFn //map的值是函数 infixParseFns map[string]infixParseFn errors []string } // 往结构体里面筛方法 func (p *Parser) registerPrefix(tokenType string, fn prefixParseFn) { p.prefixParseFns[tokenType] = fn } func (p *Parser) registerInfix(tokenType string, fn infixParseFn) { p.infixParseFns[tokenType] = fn } func NewParser(l *Lexer) *Parser { p := &Parser{ l: l, errors: []string{}, } //这个结构体加入三种方法 p.prefixParseFns = make(map[string]prefixParseFn) p.registerPrefix(INT, p.parseIntegerLiteral) p.registerPrefix(MINUS, p.parsePrefixExpression) p.registerPrefix(LPAREN, p.parseGroupedExpression) //这个加入四种方法 + - * / p.infixParseFns = make(map[string]infixParseFn) p.registerInfix(PLUS, p.parseInfixExpression) p.registerInfix(MINUS, p.parseInfixExpression) p.registerInfix(SLASH, p.parseInfixExpression) p.registerInfix(ASTERISK, p.parseInfixExpression) p.nextToken() p.nextToken() return p } func (p *Parser) ParseExpression(precedence int) Expression { prefix := p.prefixParseFns[p.curToken.Type] returnExp := prefix() for precedence < p.peekPrecedence() { infix := p.infixParseFns[p.peekToken.Type] if infix == nil { return returnExp } p.nextToken() returnExp = infix(returnExp) } return returnExp } func (p *Parser) peekPrecedence() int { if p, ok := precedences[p.peekToken.Type]; ok { return p } return LOWEST } func (p *Parser) curPrecedence() int { if p, ok := precedences[p.curToken.Type]; ok { return p } return LOWEST } func (p *Parser) peekError(t string) { msg := fmt.Sprintf("expected next token to be %s, got %s instend", t, p.peekToken.Type) p.errors = append(p.errors, msg) } func (p *Parser) expectPeek(t string) bool { if p.peekTokenIs(t) { p.nextToken() return true } else { p.peekError(t) return false } } func (p *Parser) peekTokenIs(t string) bool { return p.peekToken.Type == t } func (p *Parser) nextToken() { p.curToken = p.peekToken p.peekToken = p.l.NextToken() } func (p *Parser) parseIntegerLiteral() Expression { lit := &IntegerLiteralExpression{Token: p.curToken} value, err := strconv.ParseInt(p.curToken.Literal, 0, 64) if err != nil { msg := fmt.Sprintf("could not parse %q as integer", p.curToken.Literal) p.errors = append(p.errors, msg) return nil } lit.Value = value return lit } func (p *Parser) parsePrefixExpression() Expression { expression := &PrefixExpression{ Token: p.curToken, Operator: p.curToken.Literal, } p.nextToken() expression.Right = p.ParseExpression(PREFIX) return expression } func (p *Parser) parseGroupedExpression() Expression { p.nextToken() exp := p.ParseExpression(LOWEST) if !p.expectPeek(RPAREN) { return nil } return exp } func (p *Parser) parseInfixExpression(left Expression) Expression { expression := &InfixExpression{ Token: p.curToken, Operator: p.curToken.Literal, Left: left, } precedence := p.curPrecedence() p.nextToken() // // 通过降低优先级，来达到右结合 //if expression.Operator == "+" { // expression.Right = p.parseExpression(precedence - 1) //} else { // expression.Right = p.parseExpression(precedence) //} expression.Right = p.ParseExpression(precedence) return expression } func (p *Parser) Errors() []string { return p.errors }
