SPOJ CMEXPR 程序

SPOJ CMEXPR Program

我正在尝试解决这个问题SPOJ CMEXPR。我发现这个问题的算法是:

  1. 首先将表达式转换为后缀表达式(逆波兰表示法)
  2. 然后将后缀表达式转换为中缀表达式。

我已成功完成第一步,但在第二步遇到问题。它不会抛出任何异常,它只会给出不正确的输出。

这是我的代码:

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

class RPN{
    public String expression;
    public String output;
    public Queue<Character> queue; 

    public RPN(String exp){
        this.expression = exp;
        processRPN();
    }

    private void processRPN(){
        System.out.println("Original Infix Expression ==> " + expression);
        Queue<Character> queue = new LinkedList<Character>();
        Stack<Character> stack = new Stack<Character>();
        for(int i=0; i < expression.length(); i++){
            Character op = new Character(expression.charAt(i));
            if(op.equals('/') || op.equals('*') || op.equals('+') || op.equals('-') || op.equals('^') || op.equals('(')){
                stack.push(op);
            }
            else if(op == ')'){
                while(!stack.peek().equals('(')){
                    queue.add(stack.pop());
                }
                stack.pop();
            }
            else{
                queue.add(op);
            }
        }
        while(!stack.isEmpty()){
            queue.add(stack.pop());
        }
        displayQueue(queue);
    }   

    private void displayQueue(Queue<Character> queue){
        this.output = queue.toString();
        this.queue = queue;
    }

    public Queue<Character> getPostFixExpressionQueue(){
        return queue;
    }
}

class PIN{
    public Stack<String> finalOutputStack;
    public Queue<Character> queue;
    public static Map<Character, Integer> precedenceMap = new HashMap<Character, Integer>();    

    static{
        precedenceMap.put('-',1);
        precedenceMap.put('+',2);
        precedenceMap.put('*',3);
        precedenceMap.put('/',4);
        precedenceMap.put('^',4);
    }

    public PIN(Queue<Character> queue){
        this.queue = queue;
        processPIN();
    }

    private void processPIN(){
        System.out.println("Postfix to Infix Process Starts...");
        Character prevOp = null, currOp = null;
        Stack<String> stack = new Stack<String>();
        while(!queue.isEmpty()){
            Character peekCh = queue.peek();
            if(peekCh.equals('/') || peekCh.equals('*') || peekCh.equals('^') || peekCh.equals('+') || peekCh.equals('-')){
                if(prevOp == null && currOp == null){
                    prevOp = queue.peek();
                    currOp = queue.poll();
                }
                else{
                    prevOp = currOp;
                    currOp = queue.poll();
                }
                if(precedenceMap.get(currOp) < precedenceMap.get(prevOp)){
                    String operand2 = stack.pop();
                    String operand1 = stack.pop();
                    stack.push("("+operand1+")"+currOp.toString()+operand2);
                }
                else{
                    String operand2 = stack.pop();
                    String operand1 = stack.pop();
                    stack.push(operand1+currOp.toString()+operand2);                    
                }
            }
            else{
                stack.push(queue.poll().toString());
            }
        }
        storeOutput(stack);
    }

    private void storeOutput(Stack<String> stack){
        this.finalOutputStack = stack;
    }   
}

public class Test{
    public static void main(String h[]){
        RPN rpnObj = new RPN("(a+b)-(c-d)-(e/f)");
        System.out.println("Postfix Notation ==> " + rpnObj.output);
        PIN pinObj = new PIN(rpnObj.getPostFixExpressionQueue());
        System.out.println("Expression with Minimum Parenthesis ==> " + pinObj.finalOutputStack.toString());
    }
}

问题 1

您用于构建反向波兰表示法的算法在某些输入上产生了不正确的结果。具体来说,它将所有运算符解释为右结合运算符,并且不考虑运算符优先级。

关于右结合性,考虑输入a-b-c。您的算法错误地构造了 abc--,而正确的结果是 ab-c-。这意味着您的算法错误地将输入解释为 a-(b-c)。这种解释是 - 的右关联解释,而左关联解释是 (a-b)-c,它保留了输入 a-b-c.

的预期含义

关于运算符优先级,考虑输入a*b+c。您的算法错误地构造了 abc+*。这意味着您的算法赋予最后一个运算符 + 比第一个运算符 * 更高的优先级,将输入解释为 a*(b+c)。正确的结果应该是 ab*c+,对应于解释 (a*b)+c.

从中缀表示法正确构造反向波兰表示法所需的算法被称为 Shunting-Yard-Algorithm. See for example here,了解如何在 Java 中实现它。

问题 2

一旦您获得了正确的逆波兰表示法,您的中缀表示法重建算法就会出现另一个问题。您的方法是根据某些条件在运算符的左侧插入括号。这种方法不能在所有情况下都给出正确的结果。考虑例如 (a+b)*(c+d)。 Reverse-Polish-Notation 将是 ab+cd+*。每个添加项都需要括号,但您的方法只允许在 * 的左侧插入括号,而不能在右侧插入括号。

另外,你是否插入括号的条件是在Reverse-Polish-Notation的从左到右遍历中比较当前运算符和前一个运算符。这种做法也是不正确的,因为之前的操作员可能与当前的操作员完全无关。再考虑一下ab+cd+*。当您查看第二个 + 时,前一个运算符将是第一个 +,但它们完全无关,因为它们出现在表达式解析树的不同分支上。

要解决这个问题,您应该首先跟踪堆栈中每个元素的前一个运算符,而不是在从左到右的遍历中跟踪前一个运算符。您可以通过扩展结果堆栈来保存一对先前的运算符和结果字符串来做到这一点。或者您可以保留第二个堆栈,它只跟踪结果堆栈上每个条目的前一个运算符。

其次,您应该对操作的左侧和右侧应用运算符优先级检查,并相应地插入括号。请注意,插入括号的规则对于左右操作数是不对称的。 例如,当当前操作数是 - 时,左操作数在所有情况下都不需要括号,但如果前一个运算符是 + 或 [=15=,则右操作数需要括号].

这是一个例子:

class PIN {

  static boolean preceedsLeft(char prevOp, char currOp) {
    if (currOp == '*' || currOp == '/') {
      if (prevOp == '+' || prevOp == '-') {
        return true;
      }
    }

    return false;
  }

  static boolean preceedsRight(char prevOp, char currOp) {
    if (currOp == '-' || currOp == '*') {
      if (prevOp == '+' || prevOp == '-') {
        return true;
      }
    }

    if (currOp == '/') {
      if (prevOp == '+' || prevOp == '-' || prevOp == '*' || prevOp == '/') {
        return true;
      }
    }

    return false;
  }

  public static String process(Queue<Character> queue) {
    Stack<String> stack = new Stack<String>();
    Stack<Character> prevOp = new Stack<Character>();

    while (!queue.isEmpty()) {
      Character current = queue.poll();

      if (!current.equals('/') && !current.equals('*') &&
          !current.equals('+') && !current.equals('-')) {
        stack.push(current.toString());
        prevOp.push(current);
        continue;
      }

      Character prevOp2 = prevOp.pop();
      Character prevOp1 = prevOp.pop();

      String operand2 = stack.pop();
      String operand1 = stack.pop();

      if (preceedsLeft(prevOp1, current)) {
        operand1 = "(" + operand1 + ")";
      }

      if (preceedsRight(prevOp2, current)) {
        operand2 = "(" + operand2 + ")";
      }

      stack.push(operand1 + current + operand2);
      prevOp.push(current);
    }
    return stack.get(0);
  }
}