Я хочу знать, есть ли способ разрешить выражения infix за один проход, используя 2 стека? Стеки могут быть одно для оператора, а другое для операндов...
Стандартный способ решения с помощью алгоритма shunt-yard - преобразовать выражение infix в postfix (обратный полиш), а затем решить. Я не хочу сначала преобразовывать выражение в постфикс.
Если выражение похоже на 2*3-(6+5)+8, как решить?
Довольно поздно, но вот ответ.
Возьмите два стека:
operator stack {для операторов и круглых скобок}.operand stack.Если символ существует для чтения:
operand нажмите на operand stack, если символ (, нажмите operator stack.operator
operator stack не имеет меньшего приоритета, чем этот символ.operator от operator stack.operands (op1 и op2) из operand stack.op1 op op2 в operand stack обратно в 2.1.), выполните то же самое, что и 2.2 - 2.4, пока не встретите (.Else (больше не осталось символов для чтения):
operator stack не являются пустыми.operands и push op1 op op2 на operand stack.верните верхнее значение из operand stack.
Метод, приведенный в ссылке, действительно хорош.
Позвольте мне привести источник:
We will use two stacks:
Operand stack: to keep values (numbers) and
Operator stack: to keep operators (+, -, *, . and ^).
In the following, "process" means, (i) pop operand stack once (value1) (ii) pop operator stack once (operator) (iii) pop operand stack again (value2) (iv) compute value1 operator value2 (v) push the value obtained in operand stack.
Algorithm:
Until the end of the expression is reached, get one character and perform only one of the steps (a) through (f):
(a) If the character is an operand, push it onto the operand stack.
(b) If the character is an operator, and the operator stack is empty then push it onto the operator stack.
(c) If the character is an operator and the operator stack is not empty, and the character precedence is greater than the precedence of the stack top of operator stack, then push the character onto the operator stack.
(d) If the character is "(", then push it onto operator stack.
(e) If the character is ")", then "process" as explained above until the corresponding "(" is encountered in operator stack. At this stage POP the operator stack and ignore "(."
(f) If cases (a), (b), (c), (d) and (e) do not apply, then process as explained above.
When there are no more input characters, keep processing until the operator stack becomes empty. The values left in the operand stack is the final result of the expression.
Надеюсь, это поможет!
Ниже приведена моя попытка оценки выражения infix в java. Пожалуйста, дайте мне знать, если вы найдете какие-либо ошибки:)
import java.util.*;
public class ArithmeticExpressionEvaluation {
public static void main(String[] args) {
Scanner readExpression = new Scanner(System.in);
System.out.print("Enter the expression: ");
String expression = readExpression.nextLine();
System.out.println(expression);
System.out.println("Result: " + calculateExpression(expression));
}
public static long calculateExpression(String expression) {
Stack<Long> operandStack = new Stack<>();
Stack<Character> operatorStack = new Stack<>();
if (!isValidExpression(expression)) {
System.out.println("Not a valid expression to evaluate");
return 0;
}
int i = 0;
String currentInteger = null;
while (i < expression.length()) {
// System.out.println(expression.charAt(i));
if (expression.charAt(i) >= '0' && expression.charAt(i) <= '9') {
currentInteger = expression.charAt(i) + "";
i++;
while (i != expression.length() && (expression.charAt(i) >= '0' && expression.charAt(i) <= '9')) {
currentInteger = currentInteger + expression.charAt(i);
i++;
}
operandStack.push(Long.parseLong(currentInteger));
} else {
if (expression.charAt(i) == ')') {
while (operatorStack.peek() != '(') {
performArithmeticOperation(operandStack, operatorStack);
}
operatorStack.pop();
} else {
Character currentOperator = expression.charAt(i);
Character lastOperator = (operatorStack.isEmpty() ? null : operatorStack.peek());
if (lastOperator != null && checkPrecedence(currentOperator, lastOperator)) {
performArithmeticOperation(operandStack, operatorStack);
}
operatorStack.push(expression.charAt(i));
}
i++;
}
}
while (!operatorStack.isEmpty()) {
performArithmeticOperation(operandStack, operatorStack);
}
// System.out.println(Arrays.toString(operandStack.toArray()));
// System.out.println(Arrays.toString(operatorStack.toArray()));
return operandStack.pop();
}
public static void performArithmeticOperation(Stack<Long> operandStack, Stack<Character> operatorStack) {
try {
long value1 = operandStack.pop();
long value2 = operandStack.pop();
char operator = operatorStack.pop();
long intermediateResult = arithmeticOperation(value1, value2, operator);
operandStack.push(intermediateResult);
} catch (EmptyStackException e) {
System.out.println("Not a valid expression to evaluate");
throw e;
}
}
public static boolean checkPrecedence(Character operator1, Character operator2) {
List<Character> precedenceList = new ArrayList<>();
precedenceList.add('(');
precedenceList.add(')');
precedenceList.add('/');
precedenceList.add('*');
precedenceList.add('%');
precedenceList.add('+');
precedenceList.add('-');
if(operator2 == '(' ){
return false;
}
if (precedenceList.indexOf(operator1) > precedenceList.indexOf(operator2)) {
return true;
} else {
return false;
}
}
public static long arithmeticOperation(long value2, long value1, Character operator) {
long result;
switch (operator) {
case '+':
result = value1 + value2;
break;
case '-':
result = value1 - value2;
break;
case '*':
result = value1 * value2;
break;
case '/':
result = value1 / value2;
break;
case '%':
result = value1 % value2;
break;
default:
result = value1 + value2;
}
return result;
}
public static boolean isValidExpression(String expression) {
if ((!Character.isDigit(expression.charAt(0)) && !(expression.charAt(0) == '('))
|| (!Character.isDigit(expression.charAt(expression.length() - 1)) && !(expression.charAt(expression.length() - 1) == ')'))) {
return false;
}
HashSet<Character> validCharactersSet = new HashSet<>();
validCharactersSet.add('*');
validCharactersSet.add('+');
validCharactersSet.add('-');
validCharactersSet.add('/');
validCharactersSet.add('%');
validCharactersSet.add('(');
validCharactersSet.add(')');
Stack<Character> validParenthesisCheck = new Stack<>();
for (int i = 0; i < expression.length(); i++) {
if (!Character.isDigit(expression.charAt(i)) && !validCharactersSet.contains(expression.charAt(i))) {
return false;
}
if (expression.charAt(i) == '(') {
validParenthesisCheck.push(expression.charAt(i));
}
if (expression.charAt(i) == ')') {
if (validParenthesisCheck.isEmpty()) {
return false;
}
validParenthesisCheck.pop();
}
}
if (validParenthesisCheck.isEmpty()) {
return true;
} else {
return false;
}
}
}