Infix to Postfix 表达式中的结合性规则
Associativity rule in Infix to Postfix expression
我的 infix
到 postfix
算法使用 stack
:
static int Prec(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
static String infixToPostfix(String exp) {
String result = new String("");
Stack<Character> stack = new Stack<>();
for (int i = 0; i < exp.length(); ++i) {
char c = exp.charAt(i);
if (Character.isLetterOrDigit(c))
result += c;
else if (c == '(')
stack.push(c);
else if (c == ')') {
while (!stack.isEmpty() && stack.peek() != '(')
result += stack.pop();
stack.pop();
} else {
while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())) {
result += stack.pop();
}
stack.push(c);
}
}
while (!stack.isEmpty()) {
if (stack.peek() == '(')
return "Invalid Expression";
result += stack.pop();
}
return result;
}
输入: K+L-M*N+(O^P)*W/U/V*T+Q^J^A
预期输出: KL+MN*-OP^W*U/V/T*+QJA^^+
实际输出: KL+MN*-OP^W*U/V/T*+QJ^A^+
If current operator and operator at top of stack have same
precedence then check their associativity,
- If associativity of operators is Right to Left, then simply
push
operator onto the stack.
- If associativity of operators is Left to Right, then
pop
operator from stack and check for associativity again for current operator and operator at top of stack.
预期输出和实际输出的不同之处在于计算子表达式 ^J^A
时。
当到达字符 Q
时,堆栈包含 ['+']
。我输出操作数 Q
并移动到表达式中的下一个字符。关于上述规则,应该发生以下情况:
^
是 Q
之后的下一个字符。由于 ^
的优先级高于 +
,我将其压入堆栈,['+','^']
并将指针移动到 J
.
- 输出
J
作为操作数并移动指针。
- 指针现在位于
^
。由于栈顶还包含一个^
,它们具有相同的优先级,所以我们需要检查从右到左的关联规则。因此,我们将 ^
压入堆栈。所以堆栈看起来像 ['+','^','^']
.
- 指针现在是最后一个字符
A
所以直接输出它。
- 因为我们已经到达表达式的末尾,我们可以开始从堆栈中弹出运算符,这样子表达式的后缀形式将类似于
QJA^^+
.
但是,我的代码不适用于关联性。有人可以解释一下在上述实现中如何处理关联性吗?
这是一个简单的修复。您需要从以下位置更新 while
循环条件:
while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek()))
收件人:
while (!stack.isEmpty() && (prec(c) < prec(stack.peek()) || (prec(c) == prec(stack.peek()) && isLeftToRightAssociative(stack.peek()))))
方法如下isLeftToRightAssociative()
:
public static boolean isLeftToRightAssociative(Character operator)
{
//You can also use return operator != '^' as an alternative to the if-else given below
if (operator == '^') return false;
else return true;
}
我应该补充一点,如果用户输入包含 unary operators
的表达式,您的代码将 不会 产生正确的输出。如果您将使用 unary operators
,您应该更新您的代码。
轻松修复 -
在 else 语句之前添加另一个 else if
else if (c==stack.peek() and c=='^')
{ stack.push(c); }
我的 infix
到 postfix
算法使用 stack
:
static int Prec(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
static String infixToPostfix(String exp) {
String result = new String("");
Stack<Character> stack = new Stack<>();
for (int i = 0; i < exp.length(); ++i) {
char c = exp.charAt(i);
if (Character.isLetterOrDigit(c))
result += c;
else if (c == '(')
stack.push(c);
else if (c == ')') {
while (!stack.isEmpty() && stack.peek() != '(')
result += stack.pop();
stack.pop();
} else {
while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())) {
result += stack.pop();
}
stack.push(c);
}
}
while (!stack.isEmpty()) {
if (stack.peek() == '(')
return "Invalid Expression";
result += stack.pop();
}
return result;
}
输入: K+L-M*N+(O^P)*W/U/V*T+Q^J^A
预期输出: KL+MN*-OP^W*U/V/T*+QJA^^+
实际输出: KL+MN*-OP^W*U/V/T*+QJ^A^+
If current operator and operator at top of stack have
same
precedence then check their associativity,
- If associativity of operators is Right to Left, then simply
push
operator onto the stack.- If associativity of operators is Left to Right, then
pop
operator from stack and check for associativity again for current operator and operator at top of stack.
预期输出和实际输出的不同之处在于计算子表达式 ^J^A
时。
当到达字符 Q
时,堆栈包含 ['+']
。我输出操作数 Q
并移动到表达式中的下一个字符。关于上述规则,应该发生以下情况:
^
是Q
之后的下一个字符。由于^
的优先级高于+
,我将其压入堆栈,['+','^']
并将指针移动到J
.- 输出
J
作为操作数并移动指针。 - 指针现在位于
^
。由于栈顶还包含一个^
,它们具有相同的优先级,所以我们需要检查从右到左的关联规则。因此,我们将^
压入堆栈。所以堆栈看起来像['+','^','^']
. - 指针现在是最后一个字符
A
所以直接输出它。 - 因为我们已经到达表达式的末尾,我们可以开始从堆栈中弹出运算符,这样子表达式的后缀形式将类似于
QJA^^+
.
但是,我的代码不适用于关联性。有人可以解释一下在上述实现中如何处理关联性吗?
这是一个简单的修复。您需要从以下位置更新 while
循环条件:
while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek()))
收件人:
while (!stack.isEmpty() && (prec(c) < prec(stack.peek()) || (prec(c) == prec(stack.peek()) && isLeftToRightAssociative(stack.peek()))))
方法如下isLeftToRightAssociative()
:
public static boolean isLeftToRightAssociative(Character operator)
{
//You can also use return operator != '^' as an alternative to the if-else given below
if (operator == '^') return false;
else return true;
}
我应该补充一点,如果用户输入包含 unary operators
的表达式,您的代码将 不会 产生正确的输出。如果您将使用 unary operators
,您应该更新您的代码。
轻松修复 - 在 else 语句之前添加另一个 else if
else if (c==stack.peek() and c=='^')
{ stack.push(c); }