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

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

Также я реализовала унарный минус, деление и функции 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));

}

java@Cat

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

Tag Archives: стэк

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

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