алгоритм шунтирующего двора (в Javascript), обработка отрицательных чисел

Question

Я написал алгоритм шунтирующего двора в 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); 

Answer 1

Хорошо, поэтому я не знаю, в чем проблема с вашим кодом. Он не очень хорошо отформатирован, и он слишком длинный. Поэтому я не читал. Тем не менее, вот как бы я написал вашу программу:

Я бы разделил программу на лексический анализ и фазу синтаксического анализа. Это делает вашу программу более модульной и понятной. Я уже написал общий номер lexer и shunting yard parser. Поэтому я буду использовать их для написания программы.

Сначала, лексический анализатор (я знаю, что вы не хотите использовать регулярные выражения и что вы написали свой собственный парсер выражений, однако это вещи регулярные выражения хорошо, так):

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/

Надежда, что помогает.

Answer 2

Решение вашей проблемы может быть перезапись вступления 9-(3*(-6)) в 9-(3*(0-6)) сделать бинарный - оператора. Просто замените каждый (- в строке (0-.

Answer 3

На мой взгляд, это не правильный способ справиться с отрицательными числами в процессе лексического, как mentionded на "Aadit M шах

Я бы рекомендовал обращаться унарный + или - в пределах шунтирование-ярд алгоритму. Просто замените унарный + или - другим знаком (в моем случае «p» или «m») и обработайте их во время оценки постфиксной нотации (или RPN).

Вы можете найти мой C# реализация here on GitHub