程序员的算法趣题Q02: 四则运算组合游戏

1. 问题描述

本题来自《程序员的算法趣题》中的第2题。

在任意4个数字（0,1,2,…,9）构成的数字序列每两个数字之间中插入四则运算符{+, -, *, /}或者不插入，计算由此得到该算式的结果。

例1：’1+2-3*4’ = -9

例2：’1+23*4’ = 93, 此例中，2与3之间没有插入运算符，因此构成一个两位数

如果要求计算结果等于原数字序列逆序排列构成的四位数，求满足以上条件的数。

但是要求至少要插入一个运算符。因为一个都不插入的话，其实得到的就是原4个数字表示的四位数，那任何一个四位回文数都满足这个条件，这个结果没有什么意义。

为了避免一些trivial solution，把10的倍数都排除在外，这样确保算式评估结果以及逆序数仍然为有效的四位数。

2. 解题分析

本题涉及两个要点：

[算式的构成]

算式的构成就是构造不同的将运算符插入数字之间的组合，可以把空字符（注意，不是说white-space，而是说长度为0的字符串“”）也看成是一个运算符，插入空字符也就相当于是不插入。这样总共就有5个运算符：{‘+’, ‘-’, ‘*’, ‘/’, ‘’}，而四个数字构成的序列中共有3个位置可以插入，再扣除不能插入三个空字符‘’，因此总共有5^3-1=124种组合。

在本题中考虑用字符串的方式表示所得到的算式，比如说：‘1+2-3*4’.

构造好算式后，接下来就是计算该算式的值。

[算式值的计算]

以上第一步中所构造的算式是所谓的中序表达式，而且没有括号，属于相对简单的情况。计算机中对算式的估计通常是将算式先由中序表达式转换为逆波兰表达式，然后再对逆波兰表达式进行评估处理。

感觉这还是一个比较有意思的东西，具体算法思路将另文单独解说。

基于以上讨论，本题的处理流程如下所示：

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Thu Aug 20 08:55:36 2021

@author: chenxy
"""
import time
import random
# from   queue import Queue
from   typing import List
from   collections import deque
    
class Solution:

    def exprEval(self, expr: str) -> int:
        """
        :expr:  A string representing a fundamental expression to be evaluated
        :    
        :ret:  return the evaluation result
        """ 
        q = deque()
        k = 0

        # Handling of multi-digit number
        prev_is_digit = False        
        while k < len(expr):
            a = expr[k]
            if a.isdigit():
                if prev_is_digit:                   
                    q.append(int(a) + 10*q.pop())
                else:
                    q.append(int(a))
                    prev_is_digit = True
            else: 
                prev_is_digit = False
                q.append(a)    
            k = k + 1        

        # Handling of '*' and '/'
        # print(q)
        q1 = deque()        
        while len(q) > 0:
            a = q.popleft()
            if a == '*':
                rslt = q1.pop() * q.popleft()
                q1.append(rslt)
            elif a == '/':
                d = q.popleft()
                if d != 0:
                    rslt = q1.pop() // d  # Currently, assuming only integer division here 
                else:
                    return float('inf')
                q1.append(rslt)
            else: #if isinstance(a,int) is True:
                q1.append(a)
            
        # Now, there should be only digits and '+', '-' left in the queue
        # print(q1)
        rslt = 0
        while len(q1) > 0:
            a = q1.popleft()
            if a == '+':
                rslt = rslt + int(q1.popleft())
            elif a == '-':
                rslt = rslt - int(q1.popleft())            
            else: #if isinstance(a,int):
                rslt = a

            # print(rslt)
        return rslt
                            
    
    def op_combination(self) -> List:    
        op  = ['+', '-', '*', '/','']
        ans = []
        
        for num in range(1000,10000):
            if (num % 10) == 0:
                continue
            
            numReverse = int(str(num)[::-1])
            # print('num = {0}, numReverse = {1}'.format(num,numReverse))
            for k1 in range(len(op)):
                for k2 in range(len(op)):
                    for k3 in range(len(op)):
                        if not(k1==4 and k2==4 and k3==4):
                            numStr = str(num)
                            expr   = numStr[0] + op[k1] + numStr[1] + op[k2] + numStr[2] + op[k3] + numStr[3]
                            rslt   = self.exprEval(expr)                            

                            if numReverse == rslt:
                                print('num={0}, numReverse={1}, expr={2}, rslt={3}'.format(num,numReverse,expr,rslt))
                                ans.append([num,op[k1],op[k2],op[k3]])
        return ans

if __name__ == '__main__':        
    
    sln = Solution()

    # First, test exprEval()
    
    # expr = '1+2'
    # print(expr, ' = ', sln.exprEval(expr))

    # expr = '1+2-4*5'
    # print(expr, ' = ', sln.exprEval(expr))    

    # expr = '3*5+4-9'
    # print(expr, ' = ', sln.exprEval(expr))    

    # expr = '3*2+4/2'
    # print(expr, ' = ', sln.exprEval(expr))    

    # expr = '59*31'
    # print(expr, ' = ', sln.exprEval(expr))        
    
    # Sendondly, test op_combination()
    
    t1 = time.monotonic()
    ans = sln.op_combination()
    t2 = time.monotonic()    
    print('ans = {0}, tCost = {1}'.format(ans,(t2-t1)))

运行结果如下：

num=5931, numReverse=1395, expr=5*9*31, rslt=1395

ans = [[5931, '*', '*', '']], tCost = 4.219000000040978