我已经在JS中编写了分流码算法，它几乎适用于所有场景，但是如果我有一个负数场景，那么它就会失败，例如，如果我给出这个表达式9-(3*(-6))那么它就不会给出结果…任何提示将不胜感激．..我不想用正则表达式。我编写了自己的表达式解析器。
我的代码:
http://jsfiddle.net/min2bro/8ZvGh/20/ // ========================== Converting string into Array of opeartors & operands including brackets also======
// for example: if you enter the expression: 9-(5*2)+(7.66/3.21)*3
// this would return ['9','-','5','*','2','+','7.66','/','3.21','*','3']
output = prompt("Enter the expression");
var result = [];
var str = "";
var temp = [];
var expression = [];
for (i = 0; i < output.length; ++i)
{
if(output[i] != "*" && output[i] != "+" && output[i] != "/" && output[i] != "-" )
temp.push(output[i]);
if(output[i] == "*" || output[i] == "+" || output[i] == "-" || output[i] == "/")
{
for(var j = 0; j<= temp.length-1 ; j++ )
{
if (temp[j] == '(' || temp[j] == ')')
{
expression.push(temp[j])
}
else
{
str += temp[j];
if (temp[j+1] == ")")
{ expression.push(str);
str = "";
}
}
}
var temp = [];
if (str!="")
{
expression.push(str);
}
expression.push(output[i]);
}
str = "";
}
for(var n = 0 ; n<= temp.length-1 ; n++ )
{
if (temp[n] == '(' || temp[n] == ')')
{
expression.push(temp[n])
}
else
{
str += temp[n];
if (temp[n+1] == ")")
{ expression.push(str);
str = "";
}
}
}
if (str!="")
{
expression.push(str);
}
// ========================== Converting expression array into output array as defined in shunting algorithm
// for example: if you enter the expression: 9-(5*2)+(7.66/3.21)*3
// this would return [9,5,2,*,-,7.66,3.21,/,3,*,+]
//==============================================================================
var output = [];
var stack = [];
var precedence = {'+': 1,'-': 1,'*': 2,'/': 2,'(': 0};
for(var i = 0; i <= (expression.length-1) ; i++)
{
if(!isNaN(expression[i]))
{
output.push((expression[i]));
}
else if(expression[i] == "*" || expression[i] == "/" || expression[i] == "+" || expression[i] == "-" || expression[i] == "(" || expression[i] == ")")
{
if(stack == "" && expression[i] != ")")
{
stack.push(expression[i]);
}
else if(precedence[expression[i]] > precedence[stack[(stack.length -1)]])
{
stack.push(expression[i]);
}
else if((precedence[expression[i]] <= precedence[stack[stack.length -1]]))
{
if(expression[i] == "(")
{
stack.push(expression[i]);
}
if(stack[stack.length-1]!="(")
{
for(var k = (stack.length-1); k >= 0 ; k--)
{
output.push(stack[k]);
stack.pop(stack[k]);
}
stack.push(expression[i]);
}
}
if(expression[i] == ")")
{
for(var j = (stack.length-1); j > 0 ; j--)
{
if(stack[j]!="(")
output.push(stack[j]);
stack.pop(stack[j]);
}
}
}
//alert(stack)
if(i == expression.length-1 && expression[i] != ")")
{
//alert(stack);
for(var j = (stack.length-1); j >= 0 ; j--)
{
if(stack[j]!="(")
output.push(stack[j]);
stack.pop();
}
}
}
//alert(stack);
for(var j = (stack.length-1); j >= 0 ; j--)
{
if(stack[j]!="(")
output.push(stack[j]);
}
//============ Calculate the result===================
var result = [];
for (i = 0; i < output.length; ++i)
{
t = output[i];
//alert(t);
if (!isNaN(t))
result.push(t);
else if (t == "(" || result.length < 2)
return false;
else
{
//alert(result);
var rhs = result.pop();
//alert(rhs);
var lhs = result.pop();
// alert(rhs);
if (t == "+") result.push(parseFloat(lhs) + parseFloat(rhs));
if (t == "-") result.push(parseFloat(lhs) - parseFloat(rhs));
if (t == "*") result.push(parseFloat(lhs) * parseFloat(rhs));
if (t == "/") result.push(parseFloat(lhs) / parseFloat(rhs));
}
}
alert(result);
我认为'Aadit M Shah'提到的在标记化过程中处理负数的正确方法
我建议在分流码算法中处理一元+或-。只需将一元+或-替换为不同的符号(在我的例子中是'p'或'm')，并在计算后缀符号(或RPN)时处理它们。
你可以在GitHub上找到我的c#实现
好吧，我不知道你的代码出了什么问题。格式不好，而且太长了。所以我没有读。尽管如此，我还是会这样写你的程序:
我把程序分成词法分析和解析两个阶段。这使你的程序更模块化，更容易理解。我已经编写了一个通用词法分析器和一个分流码分析器。所以我将使用它们来编写程序。
首先，词法分析器(我知道您不想使用regex，并且您编写了自己的表达式解析器，但这正是正则表达式所擅长的，所以):
const lexer = new Lexer();
lexer.addRule(/s+/, () => {}); // skip whitespace
lexer.addRule(/[+-*/()]/, lexeme => lexeme); // punctuators: + - * / ( )
lexer.addRule(/-?(?:0|[1-9]d*)(?:.d+)?/, lexeme => +lexeme); // numbers
接下来是分厂码解析器:
const left1 = { associativity: "left", precedence: 1 };
const left2 = { associativity: "left", precedence: 2 };
const parser = new Parser({ "+": left1, "-": left1, "*": left2, "/": left2 });
然后将词法分析器连接到解析器:
Array.fromIterator = it => Array.from({ [Symbol.iterator]: () => it });
const step = value => ({ done: value === undefined, value });
const parse = input => {
lexer.setInput(input);
const next = () => step(lexer.lex());
const tokens = Array.fromIterator({ next });
return parser.parse(tokens);
};
现在您需要做的就是像下面这样调用parse函数:
const output = parse("9 - (5 * 2) + (7.66 / 3.21) * 3");
console.log(output); // [9, 5, 2, "*", "-", 7.66, 3.21, "/", 3, "*", "+"]
请自行查看输出
const lexer = new Lexer();
lexer.addRule(/s+/, () => {}); // skip whitespace
lexer.addRule(/[+-*/()]/, lexeme => lexeme); // punctuators: + - * / ( )
lexer.addRule(/-?(?:0|[1-9]d*)(?:.d+)?/, lexeme => +lexeme); // numbers
const left1 = { associativity: "left", precedence: 1 };
const left2 = { associativity: "left", precedence: 2 };
const parser = new Parser({ "+": left1, "-": left1, "*": left2, "/": left2 });
Array.fromIterator = it => Array.from({ [Symbol.iterator]: () => it });
const step = value => ({ done: value === undefined, value });
const parse = input => {
lexer.setInput(input);
const next = () => step(lexer.lex());
const tokens = Array.fromIterator({ next });
return parser.parse(tokens);
};
const output = parse("9 - (5 * 2) + (7.66 / 3.21) * 3");
console.log(output); // [9, 5, 2, "*", "-", 7.66, 3.21, "/", 3, "*", "+"]<script src="https://rawgit.com/aaditmshah/lexer/master/lexer.js"></script>
<script src="https://rawgit.com/aaditmshah/6683499/raw/875c795ec9160e095a4030e82d5a6e3416d9fdc7/shunt.js"></script>也能正确解析负数:
const output = parse("9 - (3 * (-6))");
console.log(output); // [9, 3, -6, "*", "-"]
查看演示
const lexer = new Lexer();
lexer.addRule(/s+/, () => {}); // skip whitespace
lexer.addRule(/[+-*/()]/, lexeme => lexeme); // punctuators: + - * / ( )
lexer.addRule(/-?(?:0|[1-9]d*)(?:.d+)?/, lexeme => +lexeme); // numbers
const left1 = { associativity: "left", precedence: 1 };
const left2 = { associativity: "left", precedence: 2 };
const parser = new Parser({ "+": left1, "-": left1, "*": left2, "/": left2 });
Array.fromIterator = it => Array.from({ [Symbol.iterator]: () => it });
const step = value => ({ done: value === undefined, value });
const parse = input => {
lexer.setInput(input);
const next = () => step(lexer.lex());
const tokens = Array.fromIterator({ next });
return parser.parse(tokens);
};
const output = parse("9 - (3 * (-6))");
console.log(output); // [9, 3, -6, "*", "-"]<script src="https://rawgit.com/aaditmshah/lexer/master/lexer.js"></script>
<script src="https://rawgit.com/aaditmshah/6683499/raw/875c795ec9160e095a4030e82d5a6e3416d9fdc7/shunt.js"></script>此外，它还处理优先级和结合性规则，以消除多余的括号:
const output = parse("9 - 3 * -6");
console.log(output); // [9, 3, -6, "*", "-"]
演示。
const lexer = new Lexer();
lexer.addRule(/s+/, () => {}); // skip whitespace
lexer.addRule(/[+-*/()]/, lexeme => lexeme); // punctuators: + - * / ( )
lexer.addRule(/-?(?:0|[1-9]d*)(?:.d+)?/, lexeme => +lexeme); // numbers
const left1 = { associativity: "left", precedence: 1 };
const left2 = { associativity: "left", precedence: 2 };
const parser = new Parser({ "+": left1, "-": left1, "*": left2, "/": left2 });
Array.fromIterator = it => Array.from({ [Symbol.iterator]: () => it });
const step = value => ({ done: value === undefined, value });
const parse = input => {
lexer.setInput(input);
const next = () => step(lexer.lex());
const tokens = Array.fromIterator({ next });
return parser.parse(tokens);
};
const output = parse("9 - 3 * -6");
console.log(output); // [9, 3, -6, "*", "-"]<script src="https://rawgit.com/aaditmshah/lexer/master/lexer.js"></script>
<script src="https://rawgit.com/aaditmshah/6683499/raw/875c795ec9160e095a4030e82d5a6e3416d9fdc7/shunt.js"></script>希望对你有帮助。
您的问题的解决方案可以将条目9-(3*(-6))重写为9-(3*(0-6))，以使-操作符为二进制。只需将字符串中的每个(-替换为(0-。