P1003 等价表达式

栏目: Go · 发布时间: 5年前

内容简介：懒癌患者学习Go语言，断断续续都看了几遍，可惜工作中一直没机会用上。偶然看到现在是为了学习Go来做题，和十年前信息竞赛刷一个字符串处理问题。按照做题的思路，应该是读取进来一个表达式，再将

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

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

思路

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

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

逻辑想明白，接下来就是编码实现。以为我是为了学习Go，所以有些地方刻意会写的复杂点，为了熟悉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])
        }
    }
}

赏

很惭愧，就做了一点微小的工作

P1003 等价表达式支付宝

P1003 等价表达式微信

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

Reversing

艾拉姆（Eilam,E.） / 韩琪、杨艳、王玉英、李娜 / 电子工业出版社 / 2007-9 / 79.00元

本书描述的是在逆向与反逆向之间展开的一场旷日持久的拉锯战。作者Eldad Eilam以一个解说人的身份为我们详尽地评述了双方使用的每一招每一式的优点与不足。书中包含的主要内容有：操作系统的逆向工程；.NET平台上的逆向工程；逆向未公开的文件格式和网络协议；逆向工程的合法性问题；拷贝保护和数字版权管理技术的逆向工程；防止别人对你的代码实施逆向工程的各种技术；恶意程序的逆向工程；反编译器的基本......一起来看看《Reversing》这本书的介绍吧!

码农工具