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

Как правильно реализовать алгоритм обратной польской записи, чтобы можно было работать с много-разрядными числами?
  • Вопрос задан
  • 807 просмотров
Пригласить эксперта
Ответы на вопрос 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)                      // Выполнение арифметической
               {                            // операции
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
PeoplePass Москва
от 100 000 до 250 000 руб.
ЛАНИТ Москва
До 100 000 руб.
Amigoweb Магнитогорск
от 40 000 до 70 000 руб.
06 дек. 2019, в 17:44
5000 руб./за проект
06 дек. 2019, в 17:41
1500 руб./за проект
06 дек. 2019, в 17:10
3000 руб./за проект