在调车场算法中添加一元算子

Question

我正在创建一个计算器类型的程序，该程序将输入解析为后缀表示法，然后计算表达式。它适用于+、-、*、/和^，但我无法使一元-起作用。目前，我只是想让一元函数在表达式的开头起作用。我用-5+2来测试算法。返回的结果应该是-3，但是，程序返回的是-2。我已经在我的代码中标记了两个地方，我正试图将一元符号处理为

//-------------HERE IS WHERE I TRY TO HANDLE UNARY - as "u"----------------------------

我调试了一整天，搞不清楚什么不起作用。这是我的代码：

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class Calculator {
public static void main(String[] args) {
ArrayList test = new ArrayList();
Scanner f = new Scanner(System.in);
System.out.println("Type and equation, then press enter: ");
String g = f.nextLine();
test = inputToArrayList(g);
for (int z = 0; z < test.size(); z++) {
System.out.println(test.get(z));
}
System.out.println(calculateAnswer(test));
}
public static class SyntaxErrorException extends Exception {
SyntaxErrorException(String message) {
super(message);
}
}
private static final Stack<Double> operandStack = new Stack<Double>();
private static final Stack<String> operatorStack = new Stack<String>();
private static final String OPERATORS = "+-/*%^()u";
private static final String NONBRACES = "+-/*%^u";
private static final int[] PRECEDENCE = {1, 1, 2, 2, 2, 3, 3, 3, 4};
static ArrayList<String> charList = new ArrayList<String>();
public static ArrayList inputToArrayList(String input) {
StringBuilder strBuild = new StringBuilder();
String infix = input.replace(" ", "");
try {
for (int i = 0; i < infix.length(); i++) {
char c = infix.charAt(i);
boolean isNumber = (c >= '0' && c <= '9');
//------------HERE IS WHERE I HANDLE - AT BEGINNING OF INPUT, SAVED AS U INSTEAD OF -   ----------
if (i == 0 && c == '-') {
isNumber = true;
charList.add("u");
continue;
}
if (isNumber) {
strBuild.append(c);
if (i == infix.length() - 1) {
charList.add(strBuild.toString());
strBuild.delete(0, strBuild.length());
}
} else if (c == '.') {
for (int j = 0; j < strBuild.length(); j++) {
if (strBuild.charAt(j) == '.') {
throw new SyntaxErrorException("You can't have two decimals in a number");
} else if (j == strBuild.length() - 1) {
strBuild.append(c);
j = (strBuild.length() + 1);
}
}
if (strBuild.length() == 0) {
strBuild.append(c);
}
if (i == infix.length() - 1) {
throw new SyntaxErrorException("You can't end your equation with a decimal");
}
} else if (OPERATORS.indexOf(c) != -1) {
if (strBuild.length() != 0) {
charList.add(strBuild.toString());
strBuild.delete(0, strBuild.length());
}
strBuild.append(c);
charList.add(strBuild.toString());
strBuild.delete(0, strBuild.length());
} else {
throw new SyntaxErrorException("Make sure your input only contains numbers, operators, or parantheses");
}
}
int leftParenth = 0;
int rightParenth = 0;
for (int p = 0; p < charList.size(); p++) {
String checkParenth = charList.get(p);
switch (checkParenth) {
case "(":
leftParenth++;
break;
case ")":
rightParenth++;
break;
default: //do nothing
break;
}
}
if (leftParenth != rightParenth) {
throw new SyntaxErrorException("There is not an even number of parenthesis");
}
int parenthesis = 0;
for (int f = 0; f < charList.size(); f++) {
String awesome = charList.get(f);
switch (awesome) {
case "(":
parenthesis++;
break;
case ")":
parenthesis--;
break;
default:
break;
}
if (parenthesis < 0) {
throw new SyntaxErrorException("Order of parenthesis is off");
}
}
if (NONBRACES.contains(charList.get(charList.size() - 1))) {
throw new SyntaxErrorException("The input can't end in an operator");
}
return charList;
} catch (SyntaxErrorException ex) {
System.out.println(ex);
return charList;
}
}
private static void processOperator(String op) {
if (operatorStack.empty() || op.equals("(")) {
operatorStack.push(op);
} else {
//peek the operator stack and
//let topOp be the top operator.
String topOp = operatorStack.peek();
if (precedence(op) > precedence(topOp)) {
if (!op.equals(")")) {
operatorStack.push(op);
}
} else {
//Pop all stacked operators with equal
// or higher precedence than op.
while (!operatorStack.empty() && precedence(op) >= precedence(topOp)) {
//-------------HERE IS WHERE I TRY TO HANDLE UNARY - and "u"----------------------------                   
if("u".equals(operatorStack.peek())) {
double right = operandStack.pop();
String unary = operatorStack.pop();
operandStack.push(right * (-1));
break;
}
double right = operandStack.pop();
double left = operandStack.pop();
String operator = operatorStack.pop();
switch (operator) {
case "+":
operandStack.push(left + right);
break;
case "-":
operandStack.push(left - right);
break;
case "*":
operandStack.push(left * right);
break;
case "/":
operandStack.push(left / right);
break;
case "%":
operandStack.push(left % right);
break;
case "^":
operandStack.push(Math.pow(left, right));
break;
default: //do nothing, but this should never happen
break;
}
if (topOp.equals("(")) {
//matching '(' popped - exit loop.
operandStack.push(left);
operandStack.push(right);
break;
}
if (!operatorStack.empty()) {
//reset topOp
topOp = operatorStack.peek();
}
}
//assert: Operator stack is empty or
// current operator precedence > top of stack operator precedence.
}
}
}
public static String calculateAnswer(ArrayList<String> infix) {
int p;
for (p = 0; p < infix.size(); p++) {
if (!OPERATORS.contains(infix.get(p))) {
double listIndex = Double.parseDouble(infix.get(p));
operandStack.push(listIndex);
} else {
processOperator(infix.get(p));
}
}
if (p == infix.size()) {
while (!operatorStack.empty()) {
if ("u".equals(operatorStack.peek())) {
double right = operandStack.pop();
String unary = operatorStack.pop();
operandStack.push(right * (-1));
break;
}
double right = operandStack.pop();
double left = operandStack.pop();
String current = operatorStack.pop();
switch (current) {
case "+":
operandStack.push(left + right);
break;
case "-":
operandStack.push(left - right);
break;
case "*":
operandStack.push(left * right);
break;
case "/":
operandStack.push(left / right);
break;
case "%":
operandStack.push(left % right);
break;
case "^":
operandStack.push(Math.pow(left, right));
break;
default: //do nothing, but this should never happen
break;
}
}
}
return String.valueOf(operandStack.pop());
}
private static int precedence(String op) {
return PRECEDENCE[OPERATORS.indexOf(op)];
}
}

Answer 1

这不是一个需要解决的琐碎问题。Dijkstra的原始算法明确地针对中缀运算符，并提到(但没有解决(前缀或后缀运算符。因此，没有一个简单的扩展可以通用地处理一元运算符。

您将需要存储额外的状态；具体地说，解析的最后一种元素类型以及您是否处于"反向"状态。如果它是一个运算符或什么都不是(即表达式的开头(，则"-"应切换"反向"状态。在添加到堆栈之前，数字应检查并清除反向状态和*= -1(如有必要(。换句话说，这将成为一种将一元运算符作为常量的一部分而不是运算符来处理的方式。

注意，这两段话并不矛盾！上面的解决方案不会处理3 * -(5 + 2)，因为它没有将"-"视为运算符，而是将其视为读取数字时使用的标志。

还要注意的是，这里的"正确"解决方案是，当你的操作员不是全中x时，不要使用调车场算法。使用适当的语法分析器(例如Yacc(。

Answer 2

如果我们查看编程语言的优先级表，请参阅操作顺序(维基百科(，我们会发现一元运算符与相应的中缀运算符具有不同的优先级。该表通常看起来像

1. ((括号
2. +-一元运算符
3. */乘除
4. +-中缀加法和减法
5. ===比较运算符
6. =赋值运算符

因此您的程序需要一种方法来区分具有相同符号的一元运算符和二元运算符。在Dijkstra的工作中，他给出了与*和/相同的一元减号优先级，但没有说明解析器如何区分一元和二元情况。

我已经成功地遵循了递归下降解析表达式的技术——这与调车场算法非常相似，但有一点递归来处理括号。

我们可以将语法分为两部分：前缀-后缀表达式，p，它包括数字、已识别的一元运算符(作为前缀和后缀(和方括号表达式。全表达式E是由二进制运算符分隔的一组P。

P :: number
| identifier i.e. varible name
| -P  prefix operator followed by a P
| ( E ) an E in brackets

表达式E将是

E :: P
| P + E | P - E | P * E | P / E

即在它们之间具有二进制运算符的p序列，称为p+p+p-p。

对于E部分，你使用了一个调车场，但对于p，有一点递归。他的算法是

Eparser is
var operators : Stack of Operator := empty
var operands : Stack of Tree := empty
push( operators, sentinel )
E( operators, operands )
expect( end )
return top( operands )
E( operators, operands ) is
P( operators, operands )
while next is a binary operator
pushOperator( binary(next), operators, operands )
consume
P( operators, operands )
while top(operators) not= sentinel
popOperator( operators, operands )
P( operators, operands ) is
if next is a v
push( operands, mkLeaf( v ) )
consume
else if next = "("
consume
push( operators, sentinel )   -- pushes sentinel
E( operators, operands )      -- note recursion
expect( ")" )                 -- remove bracket from input
pop( operators )              -- pops sentinel
else if next is a unary operator
pushOperator( unary(next), operators, operands )
consume
P( operators, operands )
else
error
popOperator( operators, operands ) is
if top(operators) is binary
const t1 := pop( operands )
const t0 := pop( operands )
push( operands, mkNode( pop(operators), t0, t1 ) )
else
push( operands, mkNode( pop(operators), pop(operands) ) )
pushOperator( op, operators, operands ) is
while top(operators) > op
popOperator( operators, operands )
push( op, operators )

注意，当遇到开括号时，会有一个递归步骤。首先，sentinel被推到运算符堆栈上，这是一些特殊的运算符，用于防止弹出过多的运算符。然后，代码再次调用E。E将运行，直到找到右大括号为止。当E结束时，直到第一个哨点的所有运算符都会从堆栈中弹出。