广域第一搜索：如何获得货币兑换？

Question

我正在练习一些LeetCode类问题，遇到了以下问题：

Given a list of currency pairs and the rates between these two currencies:
 
// USD = 6.4CNY, CNY = 0.13 EUR, EUR = 0.87 GBP, GBP = 89.4 INR
//
 
// Question: Input two currencies, return the rate

// Example: CNY, INR; return 10.1111
 
// Complexity?

想知道是否有任何Python3方法可以解决这个问题？看起来像是广度优先的搜索问题。关于如何解决这个问题有什么线索吗？谢谢

评论：

我在这里看到了一个解决方案：

https://leetcode.com/problems/evaluate-division/discuss/88275/Python-fast-BFS-solution-with-detailed-explantion

class Solution(object):
    
    def calcEquation(self, equations, values, queries):

        graph = {}
        
        def build_graph(equations, values):
            def add_edge(f, t, value):
                if f in graph:
                    graph[f].append((t, value))
                else:
                    graph[f] = [(t, value)]
            
            for vertices, value in zip(equations, values):
                f, t = vertices
                add_edge(f, t, value)
                add_edge(t, f, 1/value)
        
        def find_path(query):
            b, e = query
            
            if b not in graph or e not in graph:
                return -1.0
                
            q = collections.deque([(b, 1.0)])
            visited = set()
            
            while q:
                front, cur_product = q.popleft()
                if front == e:
                    return cur_product
                visited.add(front)
                for neighbor, value in graph[front]:
                    if neighbor not in visited:
                        q.append((neighbor, cur_product*value))
            
            return -1.0
        
        build_graph(equations, values)
        
        return [find_path(q) for q in queries]
    
s=Solution()

不知道如何测试这个函数

s.calcEquation('USD/CNY=?, CNY/EUR = ?, EUR/GBP = ?, GBP/INR = ?', '6.4, 0.13, 0.87, 89.4','CNY/INR=?')

给我错误信息

Traceback (most recent call last):
  File "/home/coderpad/solution.py", line 45, in <module>
    s.calcEquation('USD/CNY=?, CNY/EUR = ?, EUR/GBP = ?, GBP/INR = ?', '6.4, 0.13, 0.87, 89.4','CNY/INR=?')
  File "/home/coderpad/solution.py", line 39, in calcEquation
    build_graph(equations, values)
  File "/home/coderpad/solution.py", line 15, in build_graph
    f, t = vertices
ValueError: not enough values to unpack (expected 2, got 1)

Answer 1

我想这是可行的，但是这里不需要values变量，因为它们已经在equations中了

在这里，我们使用re.findall()来获得这三个所需的字符串（货币和比率），然后我们将循环：

import collections
import re


class Solution:
    def calcEquation(self, equations, values, queries):
        memo = collections.defaultdict(dict)
        for equation in equations:
            num, val, den = re.findall(
                r'^\s*([A-Z]{3})\s*=\s*([0-9.]+)\s*([A-Z]{3})\s*$', equation)[0]

            val = float(val)
            memo[num][num] = memo[den][den] = 1.
            memo[num][den] = val
            memo[den][num] = 1 / val

        for key in memo:
            for val in memo[key]:
                for i in memo[key]:
                    memo[val][i] = memo[val][key] * memo[key][i]

        return [memo[num].get(den, -1.) for num, den in queries]


equations = ['USD = 6.4CNY', 'CNY = 0.13 EUR', 'EUR = 0.87 GBP', 'GBP = 89.4 INR']
values = [6.4, 0.13, 0.87, 89.4]
queries = [["USD", "CNY"], ["CNY", "EUR"], ["EUR", "GBP"], ["GBP", "INR"]]

print(Solution().calcEquation(equations, queries))

从技术上讲，如果不想，您不必手动添加values。我们可以安全地删除values变量：

import collections
import re


class Solution:
    def calcEquation(self, equations, queries):
        memo = collections.defaultdict(dict)
        for equation in equations:
            num, val, den = re.findall(
                r'^\s*([A-Z]{3})\s*=\s*([0-9.]+)\s*([A-Z]{3})\s*$', equation)[0]

            val = float(val)
            memo[num][num] = memo[den][den] = 1.
            memo[num][den] = val
            memo[den][num] = 1 / val

        for key in memo:
            for val in memo[key]:
                for i in memo[key]:
                    memo[val][i] = memo[val][key] * memo[key][i]

        return [memo[num].get(den, -1.) for num, den in queries]


equations = ['USD = 6.4CNY', 'CNY = 0.13 EUR', 'EUR = 0.87 GBP', 'GBP = 89.4 INR']
queries = [["USD", "CNY"], ["CNY", "EUR"], ["EUR", "GBP"], ["GBP", "INR"]]

print(Solution().calcEquation(equations, queries))

输出

[6.399999999999987, 0.12999999999999973, 0.8699999999999983, 89.39999999999993]

正则表达式电路

jex.im可视化正则表达式：

---

如果您希望简化/更新/探索表达式，在regex101.com的右上面板中已经对其进行了解释。如果您感兴趣，可以观看匹配步骤或在this debugger link中修改它们。调试器演示了a RegEx engine如何逐步使用一些示例输入字符串并执行匹配过程

---