P1003 等价表达式

Published on 2019 / 05 / 12

前言

懒癌患者学习Go语言，断断续续都看了几遍，可惜工作中一直没机会用上。偶然看到vijos，现在已经支持Go语言。So，做题使我快乐！做题使我RP++

现在是为了学习Go来做题，和十年前信息竞赛刷vijos是完全不同的心态。当时是为了短时间内尽可能多拿分，搞不定正确的算法，也起码得按照输入数据规模把简单的三四十分拿到手。借着那本人手必读的骗分导论，暴力打表之道也偶尔发生。光阴似箭，日月如梭。扯回来，咱们来做这道题P1003 等价表达式。

思路

一个字符串处理问题。按照做题的思路，应该是读取进来一个表达式，再将a带入求值。若两个表达式a带入同一个值得到的结果相同，则认为表达式一致。可以使用多组数据，避免偶然发生的不同表达式计算结果一样的情况。整理出来，步骤如下：

读取输入数据
实现一个函数，接收一个表达式和一个变量值，返回计算结果
定义一组测试用例
将每个选项，使用测试用例进行测试，通过则认为一致，输出选项

逻辑想明白，接下来就是编码实现。出于学习Go的目的，为了熟悉相关函数和语法，有些地方不一定用最简单的方式实现逻辑。

数据输入

尝试了fmt，bufio.NewReader和bufio.NewScanner，因为输入数据有空格，fmt会把空格作为终止符，单行读取不完整。bufio.NewReader一次性读取了全部的。bufio.NewScanner比较像熟悉的readline。

表达式过滤

表达式头部尾部中间会有多余的空格，最简单的是字符串替换，过滤掉全部的空格。我用了另一种方式，使用正则表达式，留下符合要求的符号、数字和字母。多用用Go的正则表达式。多习惯一下基本数据结构string、rune、byte。

func filterExpression(expression string) string {
    // 只允许 a 数字 + - * ^ ( )
    reg, _ := regexp.Compile("[a\\d\\+\\-\\*\\^\\(\\)]+")
    mapping := func(r rune) rune {
        if reg.MatchString(string(r)) {
            return r
        }
        return -1
    }
    return strings.Map(mapping, expression)
}

表达式计算

构造并维护一个数字栈和一个操作符栈，从左至右处理表达式。遇见数字压栈；遇见a替换成数字压栈；遇见操作符，和栈顶操作符比较，优先级高压栈，否则弹出栈顶操作符和两个数字进行计算。

操作符优先级 (>^>*>+=->)，我用一个 Maps 维护，代码如下：

操作符优先级

operatorOrder["+"] = 1
operatorOrder["-"] = 1
operatorOrder["*"] = 2
operatorOrder["^"] = 3
operatorOrder["("] = 4
operatorOrder[")"] = 0

乘法和幂

因为有幂的存在，数值可能会变得很大。好在我们并不需要计算表达式的精确值，所以可以对所有涉及*和^的计算取一个大质数的模，这样可以有效避免数值过大越界。幂计算多用位运算加速。

const prime = 16769023

func powerMod(x, y int64) int64 {
    var i int64 = 1
    for j := x; y > 0; j = j * j % prime {
        if y&1 == 1 {
            i = i * j % prime
        }
        y = y >> 1
    }
    return i
}

func multiMod(x, y int64) int64 {
    return x * y % prime
}

括号处理

操作符栈只有两个括号的时候，应该弹出。测试数据应该有脏数据，有些括号不是成对的。不能直接的弹出两个了事，得做一下判断，是我们需要弹出的括号则弹出，否则不做处理。

代码

下面是AC代码，还有改进的点：

表达式过滤掉空格之后，可以在全部的操作符和a前后增加空格，然后按照空格做 split，过滤掉空元素，直接将字符串换成一个操作符、数字和a的 List，会比现在这样一次一次拿更优雅。
有些可以用 rune 的地方，还是用的 string，对这些转换很明确的话，可以更精确点。
质数随便找了一个，可以按照数据规模找一个更合适的。

全程脑袋都在想，用 Python 的，替换完字符，稍微做点处理，大概就能 eval 直接计算了吧……

/*
ZHOU Cheng <c.zhou@live.com>
2019-5-11 16:12:46
*/
package main

import (
    "bufio"
    "fmt"
    "os"
    "regexp"
    "strconv"
    "strings"
)

var operatorOrder = map[string]int{}

const Number = "1234567890"
const Mark = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

func filterExpression(expression string) string {
    // 只允许 a 数字 + - * ^ ( )
    reg, _ := regexp.Compile("[a\\d\\+\\-\\*\\^\\(\\)]+")
    mapping := func(r rune) rune {
        if reg.MatchString(string(r)) {
            return r
        }
        return -1
    }
    return strings.Map(mapping, expression)
}

func getNumOrOperator(expression string, offset int) (string, int) {
    c := expression[offset : offset+1]
    if c == "a" {
        return c, offset + 1
    }
    if _, ok := operatorOrder[c]; ok {
        return c, offset + 1
    }
    length := len(expression)
    number := ""
    for ; offset < length; offset++ {
        c := expression[offset : offset+1]
        if !strings.Contains(Number, c) {
            break
        }
        number += c
    }
    return number, offset
}

const prime = 16769023

func powerMod(x, y int64) int64 {
    var i int64 = 1
    for j := x; y > 0; j = j * j % prime {
        if y&1 == 1 {
            i = i * j % prime
        }
        y = y >> 1
    }
    return i
}

func multiMod(x, y int64) int64 {
    return x * y % prime
}

func calculateValue(val1, val2 int64, op string) int64 {
    switch op {
    case "+":
        return val1 + val2
    case "-":
        return val1 - val2
    case "*":
        return multiMod(val1, val2)
    case "^":
        return powerMod(val1, val2)
    default:
        return 0
    }
}

func calculateExpression(expression string, value int64) int64 {
    numStack := [50]int64{}
    numStackTop := 0
    opStack := [50]string{}
    opStackTop := 0

    curStr := ""
    offset := 0
    length := len(expression)
    for ; offset < length; {
        curStr, offset = getNumOrOperator(expression, offset)
        if curStr == "a" {
            numStackTop++
            numStack[numStackTop] = value
            continue
        }
        if _, ok := operatorOrder[curStr]; ok {
            curOrder, _ := operatorOrder[curStr]
            for opStackTop > 0 {
                topOrder, _ := operatorOrder[opStack[opStackTop]]
                // 如果优先级小于前面操作符，计算上一个值
                if curOrder <= topOrder && opStack[opStackTop] != "(" {
                    num1, num2 := numStack[numStackTop-1], numStack[numStackTop]
                    numStackTop -= 2
                    topOp := opStack[opStackTop]
                    opStackTop--

                    numStackTop++
                    numStack[numStackTop] = calculateValue(num1, num2, topOp)
                } else {
                    break
                }
            }
            opStackTop++
            opStack[opStackTop] = curStr

            // 检测结尾如果是 )，弹出两个括号。
            if opStack[opStackTop] == ")" {
                opStackTop--
                // 详细判断，兼容一个错误的测试用例
                if opStackTop > 0 && opStack[opStackTop] == "(" {
                    opStackTop--
                }
            }
            continue
        }
        // 最后处理数字
        num, _ := strconv.ParseInt(curStr, 10, 64)
        numStackTop++
        numStack[numStackTop] = num
    }

    // 还需要计算一次
    for ; opStackTop > 0; {
        num1, num2 := numStack[numStackTop-1], numStack[numStackTop]
        numStackTop -= 2
        op := opStack[opStackTop]
        opStackTop--

        numStackTop++
        numStack[numStackTop] = calculateValue(num1, num2, op)
    }
    return numStack[numStackTop]
}

func main() {
    scanner := bufio.NewScanner(os.Stdin)

    scanner.Scan()
    baseExpression := scanner.Text()
    baseExpression = filterExpression(baseExpression)

    scanner.Scan()
    nStr := scanner.Text()
    n, _ := strconv.Atoi(nStr)

    operatorOrder["+"] = 1
    operatorOrder["-"] = 1
    operatorOrder["*"] = 2
    operatorOrder["^"] = 3
    operatorOrder["("] = 4
    operatorOrder[")"] = 0

    const caseNum = 3
    values := [caseNum]int64{1, 3, 5}
    result := [caseNum]int64{}
    for i := 0; i < caseNum; i++ {
        result[i] = calculateExpression(baseExpression, values[i])
    }

    for offset := 0; offset < n; offset++ {
        scanner.Scan()
        expression := scanner.Text()
        expression = filterExpression(expression)
        equal := true
        for i := 0; equal && i < caseNum; i++ {
            r := calculateExpression(expression, values[i])
            if r != result[i] {
                equal = false
                break
            }
        }
        if equal {
            fmt.Print(Mark[offset : offset+1])
        }
    }
}