Алгоритм маневрового двора (в Javascript), обработка отрицательных чисел
Я написал алгоритм маневрового двора в 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);
3 ответа
Хорошо, так что я не знаю, в чем проблема с вашим кодом. Он не очень хорошо отформатирован и слишком длинный. Поэтому я не читал это. Тем не менее, вот как бы я написал вашу программу:
Я бы разделил программу на лексический анализ и этап синтаксического анализа. Это делает вашу программу более модульной и более легкой для понимания. Я уже написал общий лексер и парсинговый маневровый двор. Поэтому я буду использовать их для написания программы.
Во-первых, лексический анализатор (я знаю, что вы не хотели использовать regex и что вы написали свой собственный анализатор выражений, однако для этого хороши регулярные выражения, поэтому):
var lexer = new Lexer;
lexer.addRule(/\s+/, function () {
// skip whitespace
});
lexer.addRule(/[\+\-\*\/\(\)]/, function (lexeme) {
// punctuators: +, -, *, /, (, ).
return lexeme;
});
lexer.addRule(/\-?(?:0|[1-9]\d*)(?:\.\d+)?/, function (lexeme) {
// matches a number
// may start with an optional minus sign
// may have an optional decimal part
return +lexeme;
});
Далее у нас есть парсер маневрового двора:
var left1 = {
associativity: "left",
precedence: 1
};
var left2 = {
associativity: "left",
precedence: 2
};
var parser = new Parser({
"+": left1,
"-": left1,
"*": left2,
"/": left2
});
Затем мы подключаем лексер к парсеру:
function parse(input) {
lexer.setInput(input);
var tokens = [], token;
while (token = lexer.lex())
tokens.push(token);
return parser.parse(tokens);
}
Теперь все, что вам нужно сделать, это позвонить parse функционировать следующим образом:
var output = parse("9 - (5 * 2) + (7.66 / 3.21) * 3");
alert(JSON.stringify(output)); // [9,5,2,"*","-",7.66,3.21,"/",3,"*","+"]
Смотрите вывод для себя: http://jsfiddle.net/jwz7z7mL/
Он также правильно анализирует отрицательные числа:
var output = parse("9 - (3 * (-6))");
alert(JSON.stringify(output)); // [9,3,-6,"*","-"]
Смотрите демо: http://jsfiddle.net/jwz7z7mL/1/
Кроме того, он обрабатывает правила приоритета и ассоциативности, чтобы избавиться от лишних скобок:
var output = parse("9 - 3 * -6");
alert(JSON.stringify(output)); // [9,3,-6,"*","-"]
Демо: http://jsfiddle.net/jwz7z7mL/2/
Надеюсь, это поможет.
На мой взгляд, это неправильный способ обработки отрицательных чисел во время процесса токенизации, о чем упоминал "Aadit M Shah"
Я рекомендовал бы обращаться с унарным + или - в алгоритме маневрового двора. Просто замените унарный + или - другим знаком (в моем случае 'p' или 'm') и обрабатывайте их во время оценки записи постфикса (или RPN).
Вы можете найти мою реализацию C# здесь на GitHub
Решением вашей проблемы может быть переписывание записи 9-(3*(-6)) в 9-(3*(0-6)) сделать - оператор бинарный. Просто замените каждый (- в строке с (0-,