python - 广度优先搜索 : how to get currency exchange?

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?

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

评论:

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

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 变量:

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可能会逐步消耗一些示例输入字符串并执行匹配过程。

---