如何計算字串公式的值

距離。 兩個字串 s1 和 s2 之間的差值可以通過計算它們的最大距離來確定。

所謂距離：

將 s1 和 s2 更改為同一字串需要執行以下最少運算元。

將字元 ch1 轉換為 ch2

刪除字元。

插入字元。 例如。 s1

和 s2=“1233”;

那麼在s2中間插入4就可以得到12433，這與s1一致。

即。 d(s1,s2)

執行了插入操作）。

距離的本質。

計算兩個字串之間的距離 s1+ch1，s2+ch2 具有以下屬性：

d(s1,””

d(“”s1)

s1|d(“ch1”,”ch2”)ch1

ch2d(s1+ch1,s2+ch2)

min(d(s1,s2)+

ch1==ch2

d（s1+ch1，s2），d（s1，s2+ch2） 第乙個性質是顯而易見的。

第二性：

由於我們定義了三個操作來充當距離的度量。

因此，對於 CH1、CH2 可能僅操作。

將 ch1 變成 ch2

s1+ch1，然後刪除 ch1

d1+d(s1,s2+ch2))

S1+CH1 插入 CH2D

d(s1+ch1,s2))

2 和 3 的運算可以等同於：

在 s2+ch2 後新增 ch1

d=(1+d(s1,s2+ch2))

刪除 s2+ch2 後面的 ch2

d=(1+d(s1+ch1,s2))

因此可以得到計算距離的性質2。

複雜性分析。

從上面的屬性 2 中，我們可以看到計算過程呈現出這樣的結構（假設每一層都標有當前計算的字串長度，並假設兩個字串長度都是 .

n 正如你所看到的，問題的複雜性是指數級的。

目標。 對於n次方，對於更長的字串，時間是無法忍受的。

分析：在上面的結構中，我們發現了多次出現。

n-1,n-1),n-1,n-2)……換句話說，結構具有重疊的子問題。 此外，還存在屬性 2 的最佳子結構。 符合動態規劃演算法的基本要素。

因此，可以使用動態規劃演算法將複雜度降低到多項式水平。

動態規劃求解。

首先，為避免重複計數子問題，請新增兩個輔助陣列。

一。 儲存子問題的結果。 m[s1|

s2|其中 m[ij

表示子字串。 s1(0->i)

和。 s2(0->j)

距離。 二。 儲存字元之間的距離。

e[s1|,s2|其中。 e[

i,js[i]s[j]

三。 新的計算表示式。

按性質獲得 1. m[

m[s1i,0

s1i|;m[

0,s2js2j|;

根據性質2得到。 m[i,j

min(m[i-1,j-1]e[i,j

m[i,j-1]

m[i-1,j]

將字串拆分為字元，並將數字和運算子新增到堆疊中。

然後，找到每個運算子後，出現另乙個運算子來比較優先順序，並彈出計算，括號不算運算子，左括號與右括號相遇彈出。

注意優先順序。

例如，2*5+3 4

新增乙個數字 -->2*5+3 4

進2，進*，進5，（剛好要進+找*比+優先順序），出2*5=10進10，進+，進3，進（因為優先順序高，不要彈出），進4，剛要進，找到最高優先順序）進3個4=0，進0，剛好要進，找到最高優先順序）出10+0=0

進步，結束。