Regex删除涉及零或一的冗余乘法/除法
Regex to remove redundant multiplication/division involving zero or one?
我有一个奇怪的问题,我收到的是计算机生成的方程(作为字符串),其中偶尔会出现带有零或一个零的乘法/除法。这些方程式将以字符串形式呈现给用户
我知道我可以通过实现一种解析器来删除等式中的这些冗余部分,但我很好奇是否可以使用正则表达式来删除它们。
在我最终放弃(相当有限的)正则表达式技能之前,我想出了以下方法:
/([^'+'-]*(?:0|0'*|'*0){1,}[^'+'-]*)|(?:1'*|'*1)/g
它似乎只有在以下情况下才有效:
- 没有带零的非零数字(即没有10、20等)
- 没有否定意见
它也不能很好地使用括号。不幸的是,括号很常见。
注意,去除上述多余部分可能导致多余的括号或"括号";零";括号(即它可能变成()*x
,相当于0*x
)。多余的括号并不是一个很大的问题,但我认为";零";可以通过类似于查找CCD_ 3的第一遍的第二遍来移除括号。如果这两者中的任何一个都可以在解决问题的regex中完成,我会印象深刻。
因此,我向您介绍Stack Overflow的正则表达式大师。能做到吗?
假设
关于字符串化方程,可以假设以下情况成立:
- 不存在除以零的情况,方程将不会出现
[expr]/0
,甚至不会出现计算为[expr]/0
的表达式,如[expr]/sin(0)
- 方程本身中唯一的算子是
+
、-
、*
和/
- 减号运算符(
-
)包括减法和否定,尽管否定总是被括号包围 - 除上述操作(
sin
、cos
、pow
等)之外的任何操作都将显示为函数调用。(无^
%
等)
示例方程式
"(0+(0/0.5+(0+1*cos(p)+0*0+0*sin(p))*cos(k)+(0+1*0+0*1+0*0)*(-sin(k))+(0+1*(-sin(p))/0.5+0*0+0*cos(p))*0)*x+(0+(0+1*cos(p)+0*0+0*sin(p))*sin(k)+(0+1*0+0*1+0*0)*cos(k)+(0+1*(-sin(p))/0.5+0*0+0*cos(p))*0)*y+(0+(0+1*cos(p)+0*0+0*sin(p))*0+(0+1*0+0*1+0*0)*0+(0+1*(-sin(p))/0.5+0*0+0*cos(p))*1)*z)"
很乱,不是吗?
在留下评论后,我忍不住对它进行了破解:)
你们最大的问题是嵌套的括号。正则表达式本身在处理嵌套结构方面非常糟糕。这是我的口头禅"正则表达式是一个工具,而不是一个解决方案"的一个典型例子。
使用正则表达式作为工具,您可以对这个树结构应用某种"叶优先"(或自下而上)的方法,这就是我在第一部分while (sEq.match(...)) {...}
中所做的。之后,我可以浏览创建的array
并进行一些简单的文本编辑。
我还添加了1*
、*1
和/1
被删除,因为它们同样不会影响方程。您可以扩展它,使其足够智能,分别用0
和1
替换sin(0)
/cos(0)
,然后在某些情况下,解决方案会更小。
(正如代码注释中所提到的,如果等式包含5.0*4
之类的东西,这就中断了,因为JavaScript正则表达式没有后备,所以我相信'b
单词边界可以为我完成这项工作。不过,只需添加删除不必要小数的逻辑就可以解决这个问题。类似sEq = sEq.replace(/'.0+'b/g, '');
的东西,但我不知道这对您的用例是否必要。)
编辑:现在已修复,5.0*4
应保持原样
这还没有经过彻底的测试,欢迎反馈。
var sEq = "(0+(0/0.5+(0+1*cos(p)+0*0+0*sin(p))*cos(k)+(0+1*0+0*1+0*0)*(-sin(k))+(0+1*(-sin(p))/0.5+0*0+0*cos(p))*0)*x+(0+(0+1*cos(p)+0*0+0*sin(p))*sin(k)+(0+1*0+0*1+0*0)*cos(k)+(0+1*(-sin(p))/0.5+0*0+0*cos(p))*0)*y+(0+(0+1*cos(p)+0*0+0*sin(p))*0+(0+1*0+0*1+0*0)*0+(0+1*(-sin(p))/0.5+0*0+0*cos(p))*1)*z)";
var aParts = [];
document.getElementById('output').value = sEq + ''n';
while (sEq.match(/'([^()]*')/)) {
// while there are still "leafs", save them to aParts and replace with
// a reference to their index in aParts, making their parent a new
// "leaf" because it now doesn't contain the round brackets anymore
sEq = sEq.replace(/([a-z]*)'(([^()]*)')/gi, function(m, f, a) {
var n = aParts.length;
aParts[n] = {
'found':m,
'funct':f,
'arith':a
};
return '[' + n + ']';
});
}
for (var i = 0; i < aParts.length; i++) {
// isolate divisions/multiplications
var dms = aParts[i]['arith'].split(/(?=[+-])/);
for (var j = 0; j < dms.length; j++) {
// if the isolated part is multiplied by or divided into 0, replace with 0
if (dms[j].match(/([^.]|^)'b0[*'/]|'*0(?!'.?0*[1-9])/)) {
dms[j] = dms[j].replace(/([+-]?).*/, '$1'+'0');
}
// remove /1, *1 and 1*
dms[j] = dms[j].replace(/['/*]1'b(?!'.0*[1-9])(?:'.0*)?/g, '').replace(/([^.]|^)'b1'*/g, '$1');
}
// join back together, remove 0+, +0 and -0; 0- results in negation
aParts[i]['arith'] = dms.join('').replace(/[+-]0(?!'.?0*[1-9])(?:'.?0*)?/g, '').replace(/([^.]|^)'b0(?:'+|(-))/g, '$1$2');
// if after this the part contains just 0, perpetuate down to further eliminate
if (aParts[i]['funct']=='' && aParts[i]['arith']=='0') {
for (var j = i + 1; j < aParts.length; j++) {
if (aParts[j]['arith'].indexOf('[' + i + ']') != -1) {
aParts[j]['arith'] = aParts[j]['arith'].replace('[' + i + ']', '0');
break;
}
}
}
// add back parts previously simplified by replacing [n] with the content of aParts[n]
aParts[i]['arith'] = aParts[i]['arith'].replace(/'[('d+)']/g, function (m, n) {
return aParts[parseInt(n)]['funct'] + '(' + aParts[parseInt(n)]['arith'] + ')';
});
// This is just to show the progress of the algorithm
document.getElementById('parts').value += i + ''t' + aParts[i]['found'] + ''n';
var tmp = [];
for (var a = 0; a < aParts.length; a++) {
tmp[a] = {
'funct':aParts[a]['funct'],
'arith':aParts[a]['arith'].replace(/'[('d+)']/g, function (m, n) {
return tmp[parseInt(n)]['funct'] + '(' + tmp[parseInt(n)]['arith'] + ')';
})
};
}
// some steps didn't change after analysing, only append when significant
if (document.getElementById('output').value.indexOf(''n' + tmp[tmp.length-1]['arith'] + ''n') ==-1)
document.getElementById('output').value += tmp[tmp.length-1]['arith'] + ''n';
}
document.getElementById('solution').innerHTML =
aParts[aParts.length-1]['funct'] +
'(' + aParts[aParts.length-1]['arith'] + ')';
<h3>Parts isolated:</h3>
<textarea id="parts" rows="10" style="width:100%" wrap="off"></textarea>
<h3>Steps that simplified the equation:</h3>
<textarea id="output" rows="10" style="width:100%" wrap="off"></textarea>
<h3>Solution:</h3>
<pre id="solution"></pre>
我最终实现了一种完全非正则表达式的递归方法来解决这个问题。()
0函数本质上是通过运算符拆分每个字符串(顶级括号被分组为一个操作数),递归地对每个子部分进行操作,然后在返回函数调用链的过程中进行另一次遍历。
将其与jsperf中funkwurm的regex解决方案进行比较表明,它明显更快(至少在我个人的chrome和firefox浏览器中)。
它还没有经过彻底的测试,我相信会有改进,所以我欢迎任何反馈。
窃取funkwurm的片段显示以显示我的解决方案:
var sEq = "(0+(0/0.5+(0+1*cos(p)+0*0+0*sin(p))*cos(k)+(0+1*0+0*1+0*0)*(-sin(k))+(0+1*(-sin(p))/0.5+0*0+0*cos(p))*0)*x+(0+(0+1*cos(p)+0*0+0*sin(p))*sin(k)+(0+1*0+0*1+0*0)*cos(k)+(0+1*(-sin(p))/0.5+0*0+0*cos(p))*0)*y+(0+(0+1*cos(p)+0*0+0*sin(p))*0+(0+1*0+0*1+0*0)*0+(0+1*(-sin(p))/0.5+0*0+0*cos(p))*1)*z)";
var operators = ['+','-','*','/'];
var level = 0;
var result = cleanupEqn(sEq);
document.getElementById('solution').innerHTML = result;
function cleanupEqn(eqn){
var parts = removeRedundant(splitByParen(eqn));
level++;
document.getElementById('output').value += 'Level ' + level + ': Processing ' + eqn + ''n';
for(var i=0; i < parts.length; i++){
document.getElementById('parts').value += parts[i] + ''n';
if(parts[i].charAt(0) === '('){
// Clean up the expression inside the parentheses
var tmp = cleanupEqn(parts[i].substring(1,parts[i].length-1));
// If it was reduced to a zero, don't add the parentheses back
if(tmp === '0'){
parts[i] = '0';
}
else {
parts[i] = '(' + tmp + ')';
}
}
}
// Finally, remove redundancies again, since some might have bubbled up.
removeRedundant(parts);
document.getElementById('output').value += 'Level ' + level + ': Completed ' + eqn + ''n' + JSON.stringify(parts, null, ''t') + ''n';
level--;
// Join it all into a string and return
return parts.join('');
}
function splitByParen(str){
var out = [];
var exprStart = 0;
var count = 0;
var i;
for (i = 0; i < str.length; i++) {
var t = str.charAt(i);
if(str.charAt(i) === '('){
if(i > exprStart && count === 0){
out.push(str.substring(exprStart, i));
exprStart = i;
}
count++;
}
else if(str.charAt(i) === ')'){
count--;
if(count === 0){
out.push(str.substring(exprStart, i+1));
exprStart = i+1;
}
}
else if(count === 0 && operators.indexOf(str.charAt(i)) > -1){
if(i > exprStart){
out.push(str.substring(exprStart, i));
}
out.push(str.charAt(i));
exprStart = i+1;
}
}
// Add the last part
if(i > exprStart){
out.push(str.substring(exprStart, i));
}
return out;
}
function removeRedundant(parts) {
for(var i=0; i < parts.length; i++){
if(parts[i] === '0'){
if(i === 0){
switch(parts[i+1]){
case '*':
case '/':
if(parts[i+1] === '*' || parts[i+1] === '/'){
parts.splice(i, 3, '0');
}
else {
parts.splice(i, 2);
}
i--;
break;
case '+':
parts.splice(i, 2);
i--;
break;
case '-':
parts.splice(i, 1);
i--;
}
}
else {
switch(parts[i-1]){
case '*':
if(parts[i+1] === '*' || parts[i+1] === '/'){
// Check if the prior portion is part of a function call
if(i > 2 && operators.indexOf(parts[i-3]) < 0){
// Check if the next portion is part of a function call (or undefined)
if(i+3 < parts.length && operators.indexOf(parts[i+3]) < 0){
parts.splice(i-3, 6, '0');
i -= 4;
}
else {
parts.splice(i-3, 5, '0');
i -= 4;
}
}
else {
parts.splice(i-2, 4, '0');
i -= 3;
}
}
else {
parts.splice(i-2, 3, '0');
i -= 3;
}
break;
case '+':
case '-':
if(parts[i+1] === '*' || parts[i+1] === '/'){
// Check if the next portion is part of a function call (or undefined)
if(i+3 < parts.length && operators.indexOf(parts[i+3]) < 0){
parts.splice(i, 4, '0');
}
else {
parts.splice(i, 3, '0');
}
i--;
}
else if(parts[i+1] === '+'){
parts.splice(i-1, 2);
i -= 2;
}
else {
parts.splice(i-1, 2);
i -= 2;
}
}
}
}
else if(parts[i] === '1'){
if(i === 0){
switch(parts[i+1]){
case '*':
parts.splice(i, 2);
i--;
break;
case '+':
case '-':
if(parts[i+1] === '*'){
parts.splice(i, 2);
i--;
}
}
}
switch(parts[i-1]){
case '*':
case '/':
if(parts[i+1] !== '/'){
parts.splice(i-1, 2);
i -= 2;
}
break;
case '+':
case '-':
if(parts[i+1] === '*'){
parts.splice(i, 2);
i--;
}
}
}
}
return parts;
}
<h3>Parts isolated:</h3>
<textarea id="parts" rows="10" style="width:100%" wrap="off"></textarea>
<h3>Steps that simplified the equation:</h3>
<textarea id="output" rows="10" style="width:100%" wrap="off"></textarea>
<h3>Solution:</h3>
<pre id="solution"></pre>
<script src="new.js"></script>
- 缓存的最佳实践.避免冗余缓存
- UMD:正在分配给模块,导出冗余
- 如何更正阵列中的这种冗余
- Regex删除涉及零或一的冗余乘法/除法
- 删除方法中的冗余代码
- 多选择器冗余
- 简化冗余jquery's代码
- 排列具有相同数据的多个对象(减少冗余)
- Meteor模板-继承或外包事件以避免代码冗余
- HTML-减少HTML代码冗余
- 如果我两次使用相同的反应/冗余组件,它们会共享状态吗?
- 等待多个 ipc 调用完成,然后再继续电子/冗余
- 在 Javascript 中模拟“IN”运算符以简化冗余逻辑 OR 的最佳解决方案是什么?
- elasticsearch:保留冗余(非规范化)数据或保留 id 列表以进行交叉引用
- 如何获取调度冗余
- 编写函数以防止冗余
- 如何避免客户端验证中的冗余条件
- 同构反应-路由器-冗余同步历史中间件
- ExtJS - 如何创建可重用的函数以避免代码冗余
- 构建本地化反应/冗余应用程序的存储