S
S
Sland Show2016-08-28 14:43:21
Java
Sland Show, 2016-08-28 14:43:21

What is the best way to change the reverse polish notation algorithm?

Good day to all.
For the sake of getting acquainted with the development for Android , I decided to write a simple calculator that can accept several operators and operands at once.
For example:

2 + 3 * 4
9 / 3 + 5

I managed to write a calculator that generally works, but there is one problem. It lies in the fact that I did not succeed in implementing the Polish notation algorithm in such a way that it would be possible to count numbers whose digit is greater than one (15,250,1000, etc.).
When I wrote the calculator, I acted according to the following algorithm:
1)Трансформируем обычную запись выражения в обратную польскую нотацию
            Пример:
             2 + 3 - 2 --> 2,3+2-
             1 * 2 + 3 --> 1,2*3+

2)Затем с помощью Стека считаем результат

Here is the code of the class that converts the Polish reverse notation from regular notation:
public class ReversePolishNotationApp {

    //VARS:
    Stack<Character> stack;
    String line;
    String output;



    //INIT:
    { stack = new Stack<Character>();
        line = "";
        output = "";
    }


    //преобразует обычную запись в обратную польскую нотацию
    public void transform(String line) {
        this.line = line; //получаем инфиксную запись
        String[] arrayOfLines = line.split(""); 
        int size = line.length();

        for(int i = 0; i < size; i++) {
            char el = line.charAt(i);

            switch (el) {
                case '+':
                case '-':
                    gotOper(el,1);
                    break;
                case '×':
                case '÷':
                    gotOper(el,2);
                    break;
                case '(':
                    stack.push(el);
                    break;
                case ')':
                    gotParen(el);
                    break;
                default:
                    output = output + el;
                    break;

            }
        }

        while (!stack.isEmpty()) output += stack.pop();

    }

    private void gotOper(char currentOp, int priority) {

        while (!stack.isEmpty()) {
            char opTop = stack.pop();
            if(opTop == '(') { stack.push(opTop); break; }
            else {
                int oldPriority = -1;
                if(opTop == '+' || opTop == '-') oldPriority = 1;
                else oldPriority = 2;

                if(oldPriority < priority) { stack.push(opTop); break; }
                else output = output + opTop;
            }
        }
        stack.push(currentOp);
    }

    private void gotParen(char el1) {

        while (!stack.isEmpty()) {
            char elx = stack.pop();
            if(elx == '(') break;
            else output = output + elx;
        }
    }

    public void show() {
        System.out.println(output);
    }

    public String getNewNotation() {
        return output;
    }



}

And here is a class that counts using Stack expressions:
public class Calculate {

    //VARS:
    private Stack<Integer> stack;
    private String input;

    //INIT ALL VALUES (BY CONSTRUCTOR):
    public Calculate(String v) {
        input = v;
        stack = new Stack<Integer>();
    }


    public int doParse() {

        char ch = ' '; 
        int num1, num2, interAns;

        for(int i = 0; i < input.length(); i++) {
            ch = input.charAt(i);
            //if we works with figures (10-th notation)
            if(ch >= '0' && ch <= '9') stack.push((int) ch - '0');
            else {
                //if we work with operators
                num2 = stack.pop();
                num1 = stack.pop();
                switch (ch) {
                    case '+':
                        interAns = num1 + num2;
                        break;
                    case '-':
                        interAns = num1 - num2;
                        break;
                    case '×':
                        interAns = num1 * num2;
                        break;
                    case '÷':
                        interAns = num1 / num2;
                        break;
                    default:
                        interAns = 0;
                        break;
                }
                stack.push(interAns);
            }
        }

        interAns = stack.pop(); //финальный результат

        return interAns;
    }

}

Well, here is a screenshot of the calculator itself:
615b0abda35249caa61d0a2d9fef573e.png
How to correctly implement the reverse Polish notation algorithm so that you can work with multi-digit numbers?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
X
xmoonlight, 2016-08-28
@xmoonlight

Your parsing is character-by-character. This is not true.

for(int i = 0; i < input.length(); i++) {
            ch = input.charAt(i);
            //if we works with figures (10-th notation)
            if(ch >= '0' && ch <= '9') stack.push((int) ch - '0');
            else {

It is necessary to do it in an operator-operand way.
That is, if the character is NOT an OPERATOR ("+", "-", etc.), then it is a PART of the operand and you need to "collect" the current operand until the operator is encountered.
UPD: In general, the meaning is "collect" and when the operator is encountered - extract:
for(j=0; j<input.length(); j++)       // Для каждого символа
         {
         ch = input.charAt(j);              // Чтение символа
         theStack.displayStack(""+ch+" ");  // *диагностика*
         if(ch >= ‘0’ && ch <= ‘9’)         // Если это цифра
              operand+=ch; //Собираем строку (операнд)
         else                               // Если это оператор
            {
            theStack.push( (float)operand ); // Занести в стек, как число с плавающей точкой
            operand=''; //Обнуляем строку операнда
            num2 = theStack.pop();          // Извлечение операндов
            num1 = theStack.pop();
            switch(ch)                      // Выполнение арифметической
               {                            // операции

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question