Передо мной стояли задачи:

перевести выражение в обратную польскую нотацию;
посчитать значение выражения.

Также я реализовала унарный минус, деление и функции cube(), sqrt(), pow10().

Выражение	Обратная польская нотация	Результат
15 * -(3 — 4)	15 3 4 — u- *	15
sqrt(4) + (8 * 0.5)	4 sqrt 8 0.5 * +	6
-cube(-3)	3 u- cube u-	27
92 / 10	92 10 /	9.2
pow10(2) — 95 + 4 * 8	2 pow10 95 — 4 8 * +	37

Алгоритм перевода в обратную польскую запись:

считываем поочерёдно все лексемы, попутно убирая пробелы;
если лексема — это число или переменная, то добавляем её в результирующий список;
если лексема — это функция, то добавляем её в стэк;
если лексема — это открывающая скобка, то добавляем её в стэк;
если лексема — это закрывающая скобка, то:
- помещаем элементы из стэка в результирующую строку пока не встретим открывающую скобку, притом открывающая скобка удаляется из стэка, но в результирующую строку не добавляется;
- если на вершине стэка оказывается символ функции, то мы помещаем его из стэка в результирующую строку;
- если открывающая скока не была встречена, то скобки не согласованы.
если лексема — это оператор, то:
- если это последний символ выражения, то выражение некорректно;
- если это унарный минус, то добавляем его в стэк;
- иначе:
  - выталкиваем верхние элементы стэка в результирующую строку, пока приоритет текущего оператора меньше либо равен приоритету оператора, находящегося на верине стэка;
  - помещаем текущий оператор в стэк;
когда все данные считаны, выталкиваем все элементы стэка в результирующую строку; если в стэке оказались символы не операторов, то скобки не согласованы.

Алгоритм вычисления значения выражения в обратной польской нотации:

если в записи встретили число, то кладём его в стэк;
если в записи встретили функцию или унарный минус, то :
- вытаскиваем из стэка верхний элемент;
- применяем функцию к нему;
- кладём элемент обратно в стэк;
если в записи встретили бинарный оператор, то:
- вытаскиваем из стэка два верхних элемента;
- выполняем над ними операцию;
- кладём в стэк результат выполнения операции;
выводим последний элемент стэка.

Код программы

ideone.com

import java.util.*;
import java.lang.*;
import java.io.*;

class ExpressionParser {
	private static String operators = "+-*/";
	private static String delimiters = "() " + operators;
	public static boolean flag = true;
	private static boolean isDelimiter(String token) {
		if (token.length() != 1) return false;
		for (int i = 0; i < delimiters.length(); i++) {
			if (token.charAt(0) == delimiters.charAt(i)) return true;
		}
		return false;
	}
	
	private static boolean isOperator(String token) {
		if (token.equals("u-")) return true;
		for (int i = 0; i < operators.length(); i++) {
			if (token.charAt(0) == operators.charAt(i)) return true;
		}
		return false;
	}
	
	private static boolean isFunction(String token) {
		if (token.equals("sqrt") || token.equals("cube") || token.equals("pow10")) return true;
		return false;
	}
	
	private static int priority(String token) {
		if (token.equals("(")) return 1;
		if (token.equals("+") || token.equals("-")) return 2;
		if (token.equals("*") || token.equals("/")) return 3;
		return 4;
	}
	
	public static List<String> parse(String infix) {
		List<String> postfix = new ArrayList<String>();
		Deque<String> stack = new ArrayDeque<String>();
		StringTokenizer tokenizer = new StringTokenizer(infix, delimiters, true);
		String prev = "";
		String curr = "";
		while (tokenizer.hasMoreTokens()) {
			curr = tokenizer.nextToken();
			if (!tokenizer.hasMoreTokens() && isOperator(curr)) {
				System.out.println("Некорректное выражение.");
				flag = false;
				return postfix;
			}
			if (curr.equals(" ")) continue;
			if (isFunction(curr)) stack.push(curr);
			else if (isDelimiter(curr)) {
				if (curr.equals("(")) stack.push(curr);
				else if (curr.equals(")")) {
					while (!stack.peek().equals("(")) {
						postfix.add(stack.pop());
						if (stack.isEmpty()) {
							System.out.println("Скобки не согласованы.");
							flag = false;
							return postfix;
						}
					}
					stack.pop();
					if (!stack.isEmpty() && isFunction(stack.peek())) {
						postfix.add(stack.pop());
					}
				}
				else {
					if (curr.equals("-") && (prev.equals("") || (isDelimiter(prev)  && !prev.equals(")")))) {
						// унарный минус
						curr = "u-";
					}
					else {
						while (!stack.isEmpty() && (priority(curr) <= priority(stack.peek()))) {
							postfix.add(stack.pop());
						}
						
					}
					stack.push(curr);
				}
				
			}
			
			else {
				postfix.add(curr);
			}
			prev = curr;
		}
		
		while (!stack.isEmpty()) {
			if (isOperator(stack.peek())) postfix.add(stack.pop());
			else {
				System.out.println("Скобки не согласованы.");
				flag = false;
				return postfix;
			}
		}
		return postfix;
	}
}

class Ideone {
	public static Double calc(List<String> postfix) {
		Deque<Double> stack = new ArrayDeque<Double>();
		for (String x : postfix) {
			if (x.equals("sqrt")) stack.push(Math.sqrt(stack.pop()));
			else if (x.equals("cube")) {
				Double tmp = stack.pop();
				stack.push(tmp * tmp * tmp);
			}
			else if (x.equals("pow10")) stack.push(Math.pow(10, stack.pop()));
			else if (x.equals("+")) stack.push(stack.pop() + stack.pop());
			else if (x.equals("-")) {
				Double b = stack.pop(), a = stack.pop();
				stack.push(a - b);
			}
			else if (x.equals("*")) stack.push(stack.pop() * stack.pop());
			else if (x.equals("/")) {
				Double b = stack.pop(), a = stack.pop();
				stack.push(a / b);
			}
			else if (x.equals("u-")) stack.push(-stack.pop());
			else stack.push(Double.valueOf(x));
		}
		return stack.pop();
	}
	
	public static void main (String[] args) {
		Scanner in = new Scanner(System.in);
		String s = in.nextLine();
		ExpressionParser n = new ExpressionParser();
		List<String> expression = n.parse(s);
		boolean flag = n.flag;
		if (flag) {
			for (String x : expression) System.out.print(x + " ");
			System.out.println();
			System.out.println(calc(expression));
		}
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

import java.util.*;

import java.lang.*;

import java.io.*;

class ExpressionParser {

private static String operators = "+-*/";

private static String delimiters = "() " + operators;

public static boolean flag = true;

private static boolean isDelimiter(String token) {

if (token.length() != 1) return false;

for (int i = 0; i < delimiters.length(); i++) {

if (token.charAt(0) == delimiters.charAt(i)) return true;

}

return false;

}

private static boolean isOperator(String token) {

if (token.equals("u-")) return true;

for (int i = 0; i < operators.length(); i++) {

if (token.charAt(0) == operators.charAt(i)) return true;

}

return false;

}

private static boolean isFunction(String token) {

if (token.equals("sqrt") || token.equals("cube") || token.equals("pow10")) return true;

return false;

}

private static int priority(String token) {

if (token.equals("(")) return 1;

if (token.equals("+") || token.equals("-")) return 2;

if (token.equals("*") || token.equals("/")) return 3;

return 4;

}

public static List<String> parse(String infix) {

List<String> postfix = new ArrayList<String>();

Deque<String> stack = new ArrayDeque<String>();

StringTokenizer tokenizer = new StringTokenizer(infix, delimiters, true);

String prev = "";

String curr = "";

while (tokenizer.hasMoreTokens()) {

curr = tokenizer.nextToken();

if (!tokenizer.hasMoreTokens() && isOperator(curr)) {

System.out.println("Некорректное выражение.");

flag = false;

return postfix;

}

if (curr.equals(" ")) continue;

if (isFunction(curr)) stack.push(curr);

else if (isDelimiter(curr)) {

if (curr.equals("(")) stack.push(curr);

else if (curr.equals(")")) {

while (!stack.peek().equals("(")) {

postfix.add(stack.pop());

if (stack.isEmpty()) {

System.out.println("Скобки не согласованы.");

flag = false;

return postfix;

}

stack.pop();

if (!stack.isEmpty() && isFunction(stack.peek())) {

postfix.add(stack.pop());

}

else {

if (curr.equals("-") && (prev.equals("") || (isDelimiter(prev) && !prev.equals(")")))) {

// унарный минус

curr = "u-";

}

else {

while (!stack.isEmpty() && (priority(curr) <= priority(stack.peek()))) {

postfix.add(stack.pop());

}

stack.push(curr);

}

else {

postfix.add(curr);

}

prev = curr;

}

while (!stack.isEmpty()) {

if (isOperator(stack.peek())) postfix.add(stack.pop());

else {

System.out.println("Скобки не согласованы.");

flag = false;

return postfix;

}

return postfix;

}

class Ideone {

public static Double calc(List<String> postfix) {

Deque<Double> stack = new ArrayDeque<Double>();

for (String x : postfix) {

if (x.equals("sqrt")) stack.push(Math.sqrt(stack.pop()));

else if (x.equals("cube")) {

Double tmp = stack.pop();

stack.push(tmp * tmp * tmp);

}

else if (x.equals("pow10")) stack.push(Math.pow(10, stack.pop()));

else if (x.equals("+")) stack.push(stack.pop() + stack.pop());

else if (x.equals("-")) {

Double b = stack.pop(), a = stack.pop();

stack.push(a - b);

}

else if (x.equals("*")) stack.push(stack.pop() * stack.pop());

else if (x.equals("/")) {

Double b = stack.pop(), a = stack.pop();

stack.push(a / b);

}

else if (x.equals("u-")) stack.push(-stack.pop());

else stack.push(Double.valueOf(x));

}

return stack.pop();

}

public static void main (String[] args) {

Scanner in = new Scanner(System.in);

String s = in.nextLine();

ExpressionParser n = new ExpressionParser();

List<String> expression = n.parse(s);

boolean flag = n.flag;

if (flag) {

for (String x : expression) System.out.print(x + " ");

System.out.println();

System.out.println(calc(expression));

}

Facebook
X
Shares

7 thoughts on “Обратная польская нотация”

Александр Антоненко says: 15/12/2015 at 00:12

Решение, в общем, верное! Вообще то, задание специально подстроено для целочисленных вычислений, указано «sqrt – квадратный корень, округленный до целого,» и целочисленное деление — но Вы решили реализовать вещественные операции, тогда замените «целочисленное деление» в Вашем задании просто на деление (чтобы не переделывать всю программу).

Немного удивил факт, что calc — это метод класса Ideone, а не ExpressionParser.
И то, что вычисление функции не выведено в отдельный метод (а если еще парочку функций от одной переменной добавить — calc тогда разрастется).

Ну и главное, а что если будет задано некорректное выражение? Например, вот так. Возникает необработанная исключительная ситуация. Самое интересное, что на этапе вычисления, а на этапе перевода в обратную польскую запись вроде все ОК. Так что, пока, максимальный балл поставить не могу.

Ответить
- Mariia Illarionova says: 16/12/2015 at 01:50
  
  1) Деление исправила.
  2) Я посчитала, что выражение всегда корректное. Исправлено.
  
  Ответить
Антон says: 16/06/2016 at 23:20

Очень сложно читать из-за большой вложенности и тем более написанных в одну строку if. Нет отделения блоков по смыслу. Возможно некоторые куски стоит переписать с switch.
А так, молодец. ) Всегда перерабатывай посты с течением времени, поможет в профессиональном росте. Старый код всегда хочется переписать когда приходит понимание как сделать лучше.

Ответить
Vika says: 09/10/2020 at 16:31

Дайте пожалуйста информацию об ExpressionParser

Ответить
- Игорь Мазурок says: 25/11/2020 at 11:51
  
  На этом сайте студенты выкладывают свои индивидуальные задания для проверки их преподавателями. Большинство работ поторяют работы с cpp.mazurok.com.
  Не следует ожидать, что студенты будут откликаться на просьбы рассмотреть что-либо интересное вам. Тем более через 5 лет после сдачи экзамена.
  Просто поищмие в мнтернете, в документации по API или посмотрите исходники.
  
  Ответить
Кирилл says: 22/08/2021 at 13:08

2 1 + 3 *
простейше выражение вызывает ошибку

Ответить
- Игорь Мазурок says: 04/09/2021 at 22:43
  
  Поскольку вы не прочли, что делает программа и пытаетесь скормить ей обратную польскую запись…
  На входе программы обычные выражения типа (2 + 1) * 3, а на выходе обратная польская запись и результат вычислений.
  
  Ответить

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Обратная польская нотация

Код программы

7 thoughts on “Обратная польская нотация”

Добавить комментарий Отменить ответ