Префиксные обозначения - Java

Question

while (strToken.hasMoreTokens()) 
{ 
    String i = strToken.nextToken();    
    char ch = ' '; 
    ch = i.charAt(0); 
    int operand; 
    int operator; 

    if(Character.isDigit(ch)) 
    { 
     operand = Integer.parseInt(i); 
     operandStack.push(operand); 
    } 
    else 
    { 
     operator = i.charAt(0); 
     operatorStack.push(operator); 
    } 
} 

while(operandStack.size() > 1) 
{ 
    operandStack.push(operate(operandStack.pop(), 
    operandStack.pop(), operatorStack.pop())); 
} 

resultTextField.setText(Integer.toString(operandStack.peek())); 

Мой код не оценивает операнды в префиксах. Как его пересмотреть, чтобы оценить операнды в префиксной нотации.

Answer 1

Вы заполняете свой стек, а затем начинаете оценивать, вместо этого, когда вы сталкиваетесь с оператором во время сканирования, вы должны вывести операнды, вычислить результат (путем применения встречного оператора к операндам) и направить результат в стек. Сканирование справа налево. Если вы сканируете слева направо, алгоритм отличается. Вы можете прочитать обо всех реализациях на странице wikipedia на польской нотации.

Что вы делаете сейчас:

input: * + 16 4 + 3 1 
operand stack: 16 4 3 1 
operator stack: * + + 
pop + pop 3 pop 1 push 4 
operand stack: 16 4 4 
operator stack: * + 
pop + pop 4 pop 4 push 8 
operand stack: 16 8 
operator stack: * 
pop * pop 8 pop 16 
result = 16 * 128 

Что вам нужно сделать (справа налево):

input: * + 16 4 + 3 1 
push 1 push 3 
operand stack: 1 3 
operator: + (you don't need operator stack) 
pop 1 pop 3 push 3+1 = 4 
operand stack: 4 
push 4 push 16 
operand stack: 4 4 16 
operator + 
pop 16 pop 4 push 4+16 = 20 
operand stack: 4 20 
operator * 
pop 20 pop 4 result 4*20 = 80