SlandShow
@SlandShow
70% of my body is made of movies.

Каким способом стоит переделать алгоритм обратной польской записи?

Всем доброго времени суток.

Ради ознакомления с разработкой под Android решил написать простой калькулятор, который может принимать сразу несколько операторов и операндов.

Например:
2 + 3 * 4
9 / 3 + 5


Мне удалось написать калькулятор, который в целом работает, но есть одна проблема. Она заключается в том, что у меня не вышло реализовать алгоритм польской записи именно таким образом, чтобы можно было считать числа, разряд которых больше одного (15,250,1000 и т.д.).

Когда я писал калькулятор, то я действовал по следующему алгоритму:
1)Трансформируем обычную запись выражения в обратную польскую нотацию
            Пример:
             2 + 3 - 2 --> 2,3+2-
             1 * 2 + 3 --> 1,2*3+

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


Вот код класса, который превращает из обычной записи польскую обратную запись:

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;
    }



}


А вот класс, который считает с помощью Стека выражения:
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;
    }

}


Ну а вот скриншот самого калькулятора:
615b0abda35249caa61d0a2d9fef573e.png

Как правильно реализовать алгоритм обратной польской записи, чтобы можно было работать с много-разрядными числами?
  • Вопрос задан
  • 953 просмотра
Пригласить эксперта
Ответы на вопрос 1
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
У Вас парсинг - посимвольный. Это неверно.
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 {

Нужно его делать по-операторно-операндным.
Т.е., если символ - НЕ ОПЕРАТОР ("+","-" и т.д.), значит это ЧАСТЬ операнда и нужно "собирать" текущий операнд, пока не встретится оператор.
UPD: В целом, смысл "собирать" и когда встретится оператор - извлечь:
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)                      // Выполнение арифметической
               {                            // операции
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы