使用堆栈添加到Postfix中Java
问题描述：
我正在尝试编写一个程序来将中缀表达式转换为后缀表达式。使用堆栈添加到Postfix中Java
，我使用的算法如下：
1. Create a stack
2. For each character t in the expression
- If t is an operand, append it to the output
- Else if t is ')',then pop from the stack till '(' is encountered and append
it to the output. do not append '(' to the output.
- If t is an operator or '('
-- If t has higher precedence than the top of the stack, then push t
on to the stack.
-- If t has lower precedence than top of the stack, then keep popping
from the stack and appending to the output until either stack is
empty or a lower priority operator is encountered.
After the input is over, keep popping and appending to the output until the
stack is empty.
这里是我的代码打印出错误的结果。
public class InfixToPostfix
{
private static boolean isOperator(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'
|| c == '(' || c == ')';
}
private static boolean isLowerPrecedence(char op1, char op2)
{
switch (op1)
{
case '+':
case '-':
return !(op2 == '+' || op2 == '-');
case '*':
case '/':
return op2 == '^' || op2 == '(';
case '^':
return op2 == '(';
case '(':
return true;
default:
return false;
}
}
public static String convertToPostfix(String infix)
{
Stack<Character> stack = new Stack<Character>();
StringBuffer postfix = new StringBuffer(infix.length());
char c;
for (int i = 0; i < infix.length(); i++)
{
c = infix.charAt(i);
if (!isOperator(c))
{
postfix.append(c);
}
else
{
if (c == ')')
{
while (!stack.isEmpty() && stack.peek() != '(')
{
postfix.append(stack.pop());
}
if (!stack.isEmpty())
{
stack.pop();
}
}
else
{
if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
{
stack.push(c);
}
else
{
while (!stack.isEmpty() && isLowerPrecedence(c, stack.peek()))
{
Character pop = stack.pop();
if (pop != '(')
{
postfix.append(pop);
}
}
}
stack.push(c);
}
}
}
return postfix.toString();
}
public static void main(String[] args)
{
System.out.println(convertToPostfix("A*B-(C+D)+E"));
}
}
程序应该打印AB*CD+-E+但打印AB*-CD+E。 为什么输出不正确？
此外，是否有一个更优雅的解决这个问题。请分享，如果你有或知道一个。
答
问题是与你的其他部分：
if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
{
stack.push(c);
}
else
{
while (!stack.isEmpty() && isLowerPrecedence(c, stack.peek()))
{
Character pop = stack.pop();
if (pop != '(')
{
postfix.append(pop);
}
}
}
stack.push(c);
所以在这里你与stack.push（）当你看到堆栈不为空和优先级的比赛是推高相同的C元素的两倍。
所以把这个stack.push放在其他部分中，或者从if条件中删除推送。
另一个问题是，当最后你在堆栈中有一些操作符时，你不会弹出它们。
这里就是我想出了你的情况下，代码：我觉得上面的回答
private static boolean isOperator(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^'
|| c == '(' || c == ')';
}
private static boolean isLowerPrecedence(char op1, char op2)
{
switch (op1)
{
case '+':
case '-':
return !(op2 == '+' || op2 == '-');
case '*':
case '/':
return op2 == '^' || op2 == '(';
case '^':
return op2 == '(';
case '(':
return true;
default:
return false;
}
}
public static String convertToPostfix(String infix)
{
Stack<Character> stack = new Stack<Character>();
StringBuffer postfix = new StringBuffer(infix.length());
char c;
for (int i = 0; i < infix.length(); i++)
{
c = infix.charAt(i);
if (!isOperator(c))
{
postfix.append(c);
}
else
{
if (c == ')')
{
while (!stack.isEmpty() && stack.peek() != '(')
{
postfix.append(stack.pop());
}
if (!stack.isEmpty())
{
stack.pop();
}
}
else
{
if (!stack.isEmpty() && !isLowerPrecedence(c, stack.peek()))
{
stack.push(c);
}
else
{
while (!stack.isEmpty() && isLowerPrecedence(c, stack.peek()))
{
Character pop = stack.pop();
if (c != '(')
{
postfix.append(pop);
} else {
c = pop;
}
}
stack.push(c);
}
}
}
}
while (!stack.isEmpty()) {
postfix.append(stack.pop());
}
return postfix.toString();
}
public static void main(String[] args)
{
System.out.println(convertToPostfix("A*B-(C+D)+E"));
}
答
是不正确的。
这是我修正版本：。
package Stack;
import java.util.Stack;
/*
*
Algorithm
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
…..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty), push it.
…..3.2 Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the precedence of the operator residing on the top of the stack. Push the scanned operator to the stack.
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘ is encountered.
6. Repeat steps 2-6 until infix expression is scanned.
7. Pop and output from the stack until it is not empty.
*/
public class InfixToPostFixEvalution {
private static boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '(' || c == ')';
}
private static int getPrecedence(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
// A utility function to check if the given character is operand
private static boolean isOperand(char ch) {
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
public static String convertToPostfix(String infix) {
Stack<Character> stack = new Stack<Character>();
StringBuffer postfix = new StringBuffer(infix.length());
char c;
for (int i = 0; i < infix.length(); i++) {
c = infix.charAt(i);
if (isOperand(c)) {
postfix.append(c);
} else if (c == '(') {
stack.push(c);
}
// If the scanned character is an ‘)’, pop and output from the stack
// until an ‘(‘ is encountered.
else if (c == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
postfix.append(stack.pop());
}
if (!stack.isEmpty() && stack.peek() != '(')
return null;
else if(!stack.isEmpty())
stack.pop();
}
else if (isOperator(c)) // operator encountered
{
if (!stack.isEmpty() && getPrecedence(c) <= getPrecedence(stack.peek())) {
postfix.append(stack.pop());
}
stack.push(c);
}
}
while (!stack.isEmpty()) {
postfix.append(stack.pop());
}
return postfix.toString();
}
public static void main(String[] args) {
System.out.println(convertToPostfix("a+b*(c^d-e)^(f+g*h)-i"));
}
}
答
此代码插入了“（”以及在堆栈，并相应去除实施缀以后缀的只是另一种方式在这里检查，直到我做在堆栈中找不到优先级较低的操作符我会弹出该值，例如，如果堆栈有 - 并且下一个操作符是+，它将弹出 - 因为它具有相同的优先级。由java提供也可以使用到位
import chapter4.LinkedListStack(custom stack implementation);
public class InfixToPostfix {
public String infixToPostfix(String str) {
LinkedListStack<String> stack = new LinkedListStack<>();
String[] st = str.split("");
String result = "";
for (String s : st) {
if (operator(s)) {
if (")".equals(s)) {
while (!stack.isEmpty() && !"(".equals(stack.getTop())) {
result += stack.pop();
}
if (!stack.isEmpty()) {
stack.pop();
}
} else {
if (!stack.isEmpty() && !isLowerPrecedence(s, stack.getTop())) {
stack.push(s);
} else {
while (!stack.isEmpty() && isLowerPrecedence(s, stack.getTop())) {
String top = stack.pop();
if (!"(".equals(top)) {
result += top;
}
}
stack.push(s);
}
}
} else {
result += s;
}
}
while (!stack.isEmpty()) {
result += stack.pop();
}
return result;
}
private boolean isLowerPrecedence(String s, String s1) {
switch (s) {
case "+":
return !("+".equals(s1) || "(".equals(s1));
case "-":
return !("-".equals(s1) || "(".equals(s1));
case "*":
return "/".equals(s1) || "^".equals(s1) || "(".equals(s1);
case "/":
return "*".equals(s1) || "^".equals(s1) || "(".equals(s1);
case "^":
return "(".equals(s1);
case "(":
return false;
default:
return false;
}
}
private boolean operator(String s) {
return "+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s) || "^".equals(s) || "(".equals(s) ||
")".equals(s);
}
public static void main(String[] args) {
InfixToPostfix itp = new InfixToPostfix();
System.out.println("The Postfix expression for A*B-(C+D)+E is: " + itp.infixToPostfix("A*B-(C+D)+E"));
System.out.println("The Postfix expression for 1+2*4/5-7+3/6 is: " + itp.infixToPostfix("1+2*4/5-7+3/6"));
System.out.println("The Postfix expression for a+(b*c)/d is: " + itp.infixToPostfix("a+(b*c)/d"));
}
}
public class LinkedListStack<E> {
private Node<E> head;
private static class Node<E> {
E item;
Node<E> next;
public Node(E item, Node<E> next) {
this.item = item;
this.next = next;
}
}
public void push(E item) {
System.out.println("push: " + item);
Node<E> newNode = new Node<>(item, null);
newNode.next = head;
head = newNode;
}
public E pop() {
if (isEmpty()) {
System.out.println("stack is Empty -> empty stack exception");
return null;
}
System.out.println("pop: " + head.item);
E data = head.item;
head = head.next;
return data;
}
public boolean isEmpty() {
return head == null;
}
public E getTop() {
return head.item;
}
}
调试一下，看看自己.. – SMA 2014-11-02 12:07:17
我调试它..不能找到这样贴在这里！ – OneMoreError 2014-11-02 12:09:16