UVA 215 电子表格计算器

左手的ㄟ右手 2022-05-15 23:18 108阅读 0赞

> 电子表格计算器 UVA - 215
> 
> A spreadsheet is a rectangular array of cells. Cells contain data or expressions that can be evaluated to  
> obtain data. A “simple” spreadsheet is one in which data are integers and expressions are mixed sums  
> and differences of integers and cell references. For any expression, if each cell that is referenced contains  
> an integer, then the expression can be replaced by the integer to which the expression evaluates. You  
> are to write a program which evaluates simple spreadsheets.  
> Input  
> Input consists of a sequence of simple spreadsheets. Each spreadsheet begins with a line specifying the  
> number of rows and the number of columns. No spreadsheet contains more than 20 rows or 10 columns.  
> Rows are labeled by capital letters A through T. Columns are labeled by decimal digits 0 through 9.  
> Therefore, the cell in the first row and first column is referenced as A0; the cell in the twentieth row  
> and fifth column is referenced as T4.  
> Following the specification of the number of rows and columns is one line of data for each cell,  
> presented in row-major order. (That is, all cells for the first row come first, followed by all cells for the  
> second row, etc.)  
> Each cell initially contains a signed integer value or an expression involving unsigned integer constants,  
> cell references, and the operators + (addition) and - (subtraction).  
> If a cell initially contains a signed integer, the corresponding input line will begin with an optional  
> minus sign followed by one or more decimal digits.  
> If a cell initially contains an expression, its input line will contain one or more cell references or  
> unsigned integer constants separated from each other by + and - signs. Such a line must begin with  
> a cell reference. No expression contains more than 75 characters. No line of input contains leading  
> blanks. No expression contains any embedded blanks. However, any line may contain trailing blanks.  
> The end of the sequence of spreadsheets is marked by a line specifying 0 rows and 0 columns.  
> Output  
> For each spreadsheet in the input, you are to determine the value of each expression and display  
> the resulting spreadsheet as a rectangular array of numbers with the rows and columns appropriately  
> labeled. In each display, all numbers for a column must appear right-justified and aligned with the  
> column label.  
> Operators are evaluated left to right in each expression; values in cells are always less than 10000  
> in absolute value. Since expressions may reference cells that themselves contain expressions, the order  
> in which cells are evaluated is dependent on the expressions themselves.  
> If one or more cells in a spreadsheet contain expressions with circular references, then the output  
> for that spreadsheet should contain only a list of the unevaluated cells in row-major order, one per line,  
> with each line containing the cell label, a colon, a blank, and the cell’s original expression.  
> A blank line should appear following the output for each spreadsheet.  
> Sample Input  
> 2 2  
> A1+B1  
> 5  
> 3  
> B0-A1  
> 3 2  
> A0  
> 5  
> C1  
> 7  
> A1+B1  
> B0+A1  
> 0 0  
> Sample Output  
> 0 1  
> A 3 5  
> B 3 -2  
> A0: A0  
> B0: C1  
> C1: B0+A1

**意为给出表格，模拟表格计算表格的数值，如果能计算出结果，就输出表格的结果。如果不能，就输出无法计算的表格。**  
此题核心主要是一个递归。  
其次也有无法输出的情况，也就是循环调用了表格，就会出现无法计算。  
也有一个值得注意的地方比如，A0：A0-A0，这个就是无法计算的，而并不是0。  
一开始因为有个取负的符号在，而且涉及到运算。所以才考虑用python，后来发现python似乎并不能简化此题，但是已经写了很多，也就那么写了下去。此间有很多还可以优化的地方，比如递归处代码冗余，其实可以写成函数，几个调用就成。  
此题可能c语言会更好。

def init():
        for i in range(a):
            data[chr(ord('A')+i)]=[]
            datas[chr(ord('A') + i)] = []
    
    def dfs(char,j):
        if j<b and  datas[char][j]!=-999999:
            return datas[char][j]
    
        temp=data[char][j]
        sum=0
        start=0
        end=len(temp)
        while 1:
            fh=temp.find('+',start,end)
            if fh!=-1:
                if temp[fh+1].isalpha():
                    if ord(temp[fh+1])>ord('A')+a-1:
                        return -999999
                    if  fh+3<end and temp[fh+3].isdigit():
                        if temp[fh+1:fh+4] not in xh:
                            if int(temp[fh+2:fh+4])>=b:
                                return -999999
                            if datas[temp[fh + 1]][int(temp[fh+2:fh+4])]==-999999:
                                xh.append(temp[fh+1:fh+4])
                        else:
                            xh.clear()
                            return -999999
                        tempt=dfs(temp[fh+1],int(temp[fh+2:fh+4]))
                        if tempt==-999999:
                            return tempt
                        else:
                            sum+=tempt
                            start=fh+4
                    else:
                        if temp[fh+1:fh+3] not in xh :
                            if int(temp[fh+2])>=b:
                                return -999999
                            if datas[temp[fh + 1]][int(temp[fh+2])]==-999999:
                                xh.append(temp[fh+1:fh+3])
                        else:
                            xh.clear()
                            return -999999
                        tempt = dfs(temp[fh + 1], int(temp[fh+2]))
                        if tempt==-999999:
                            return tempt
                        else:
                            sum+=tempt
                            start=fh+3
                else:
                    k=2
                    tsum=int(temp[fh+1])
                    while fh+k<end and temp[fh+k].isdigit():
                        tsum=tsum*10+int(temp[fh+k])
                        k=k+1
                    start=fh+k
                    sum=sum+tsum
            else:
                break
        start = 0
        end = len(temp)
        while 1:
            fh=temp.find('-',start,end)
            if fh!=-1:
                if temp[fh + 1].isalpha():
                    if ord(temp[fh+1])>ord('A')+a-1:
                        return -999999
                    if  fh+3<end and temp[fh+3].isdigit():
                        if temp[fh+1:fh+4] not in xh :
                            if int(temp[fh+2:fh + 4])>=b:
                                return -999999
                            if datas[temp[fh + 1]][int(temp[fh+2:fh + 4])]==-999999:
                                xh.append(temp[fh+1:fh+4])
                        else:
                            xh.clear()
                            return -999999
                        tempt=dfs(temp[fh+1],int(temp[fh+2:fh+4]))
                        if tempt==-999999:
                            return tempt
                        else:
                            sum-=tempt
                            start=fh+4
    
                    else:
                        if temp[fh+1:fh+3] not in xh:
                            if int(temp[fh+2])>=b:
                                return -999999
                            if datas[temp[fh + 1]][int(temp[fh+2])]==-999999:
                                xh.append(temp[fh+1:fh+3])
                        else:
                            xh.clear()
                            return -999999
                        tempt = dfs(temp[fh + 1], int(temp[fh + 2]))
                        if tempt==-999999:
                            return tempt
                        else:
                            sum-=tempt
                            start=fh+3
                elif temp[0]=='-':
                    sum-=int(temp[1:])
                    start=1
    
                else:
                    k = 2
                    tsum = int(temp[fh + 1])
                    while fh+k<end and temp[fh + k].isdigit():
                        tsum = tsum * 10 + int(temp[fh + k])
                        k = k + 1
                    start=fh+k
                    sum = sum - tsum
            else:
                break
    
        if temp[0].isalpha():
            if ord(temp[fh + 1]) > ord('A') + a - 1:
                return -999999
            if len(temp)>2 and temp[2].isdigit():
                if temp[:3] not in xh :
                    if int(temp[1:3])>=b:
                        return -999999
                    if datas[temp[0]][int(temp[1:3])]==-999999:
                        xh.append(temp[:3])
                else:
                    return -999999
                tempt=dfs(temp[0], int(temp[1:3]))
                if tempt==-999999:
                    return tempt
                else:
                    sum+=tempt
            else:
                if temp[:2] not in xh:
                    if int(temp[1])>=b:
                        return -999999
                    if datas[temp[0]][int(temp[1])]==-999999:
                        xh.append(temp[:2])
                else:
                    return -999999
                tempt=dfs(temp[0], int(temp[1]))
                if tempt==-999999:
                    return tempt
                else:
                    sum+=tempt
        elif temp[0]!='-':
            k = 1
            tsum = int(temp[0])
            while k<end and temp[k].isdigit():
                tsum = tsum * 10 + int(temp[k])
                k = k + 1
            sum = sum + tsum
        datas[char][j]=sum
        for x in xh:
            if datas[x[0]][int(x[1:])]!=-999999:
                xh.remove(x)
        return sum
    
    
    
    
    
    
    
    
    if __name__=='__main__':
        while 1:
            a, b = map(int, input().split())
            if a==0 and b==0:
                break
            data={}
            datas = {}
            init()
            xh = []
            f=1
        #    a,b=map(int,input().split())
            for i in range(a):
                for j in range(b):
                    s=input()
                    if s.isdigit() or (s[0]=='-' and s[1:].isdigit()):
                        datas[chr(ord('A')+i)].append(int(s))
                    else:
                        datas[chr(ord('A') + i)].append(-999999)
                    data[chr(ord('A')+i)].append(s)
    
            for i in range(a):
                for j in range(b):
                    if datas[chr(ord('A')+i)][j]==-999999:
                        if dfs(chr(ord('A')+i),j)==-999999:
                            f=0
            if f:
                print(' ',end='')
                for j in range(b):
                    print('%6d'%(j),end='')
                print()
                for i in range(a):
                    print(chr(ord('A')+i),end='')
                    for j in range(b):
    
                        print('%6d'%(datas[chr(ord('A')+i)][j]),end='')
                    print()
            else:
                for i in range(a):
                    for j in range(b):
                        if datas[chr(ord('A') + i)][j] == -999999:
                            print(chr(ord('A')+i)+str(j)+': '+data[chr(ord('A')+i)][j])
            print()