怎么计算一个字符串公式的值
发布网友
发布时间：2022-04-22 01:10
共2个回答
热心网友
时间：2023-07-11 03:58
编辑距离
关于两个字符串s1,s2的差别，可以通过计算他们的最小编辑距离来决定。
所谓的编辑距离:
让s1和s2变成相同字符串需要下面操作的最小次数。
1.
把某个字符ch1变成ch2
2.
删除某个字符
3.
插入某个字符
例如
s1
=
“12433”
和s2=”1233”;
则可以通过在s2中间插入4得到12433与s1一致。
即
d(s1,s2)
=
1
(进行了一次插入操作)
编辑距离的性质
计算两个字符串s1+ch1,
s2+ch2的编辑距离有这样的性质:
1.
d(s1,””)
=
d(“”,s1)
=
|s1|
d(“ch1”,”ch2”)
=
ch1
==
ch2
?
0
:
1;
2.
d(s1+ch1,s2+ch2)
=
min(
d(s1,s2)+
ch1==ch2
?
0
:
1
,
d(s1+ch1,s2),
d(s1,s2+ch2)
);
第一个性质是显然的。
第二个性质:
由于我们定义的三个操作来作为编辑距离的一种衡量方法。
于是对ch1,ch2可能的操作只有
1.
把ch1变成ch2
2.
s1+ch1后删除ch1
d
=
(1+d(s1,s2+ch2))
3.
s1+ch1后插入ch2
d
=
(1
+
d(s1+ch1,s2))
对于2和3的操作可以等价于:
_2.
s2+ch2后添加ch1
d=(1+d(s1,s2+ch2))
_3.
s2+ch2后删除ch2
d=(1+d(s1+ch1,s2))
因此可以得到计算编辑距离的性质2。
复杂度分析
从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记，并假设两个串长度都为
n
)
可以看到，该问题的复杂度为指数级别
3
的
n
次方，对于较长的串，时间上是无法让人忍受的。
分析:
在上面的结构中，我们发现多次出现了
(n-1,n-1),
(n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。
动态规划求解
首先为了避免重复计算子问题，添加两个辅助数组。
一.
保存子问题结果。
m[
|s1|
,|s2|
]
,
其中m[
i
,
j
]
表示子串
s1(0->i)
与
s2(0->j)
的编辑距离
二.
保存字符之间的编辑距离.
e[
|s1|,
|s2|
]
,
其中
e[
i,
j
]
=
s[i]
=
s[j]
?
0
:
1
三.
新的计算表达式
根据性质1得到
m[
0,0]
=
0;
m[
s1i,
0
]
=
|s1i|;
m[
0,
s2j
]
=
|s2j|;
根据性质2得到
m[
i,
j
]
=
min(
m[i-1,j-1]
+
e[
i,
j
]
,
m[i,
j-1]
,
m[i-1,
j]
);
热心网友
时间：2023-07-11 03:58
把字符串拆成字符，将数字和运算符加入栈。
然后每发现运算符后出现了另一个运算符比较优先级高低，弹出计算，括号不算运算符，左括号遇到右括号弹出。
注意优先级。
比如2*5+3/4
加一个#号--> 2*5+3/4#
进2，进*，进5，（刚要进+发现*比+优先），出2*5=10
进10，进+，进3，进/（因为/优先级高，不弹出），进4，
（刚要进#，发现#优先级最高）出3/4 = 0，进0，
（刚要进#，发现#优先级最高）出10+0 = 0
进#，结束
