将一元运算符添加到”Shunting Yard”算法中。

huangapple
go评论75阅读模式
英文:

Adding unary operator to shunting yard algorithm

问题

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Calculator {

    public static void main(String[] args) {
        ArrayList<String> test = new ArrayList<String>();
        Scanner f = new Scanner(System.in);

        System.out.println("Type an 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<String> 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');
                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 parentheses");
                }
            }

            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 parentheses");
            }

            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 parentheses 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 {
            String topOp = operatorStack.peek();
            if (precedence(op) > precedence(topOp)) {
                if (!op.equals(")")) {
                    operatorStack.push(op);
                }
            } else {
                while (!operatorStack.empty() && precedence(op) >= precedence(topOp)) {
                    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:
                            break;
                    }

                    if (topOp.equals("(")) {
                        operandStack.push(left);
                        operandStack.push(right);
                        break;
                    }

                    if (!operatorStack.empty()) {
                        topOp = operatorStack.peek();
                    }
                }
            }
        }
    }

    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:
                        break;
                }
            }
        }
        return String.valueOf(operandStack.pop());
    }

    private static int precedence(String op) {
        return PRECEDENCE

<details>
<summary>英文:</summary>

I am creating a calculator-type program that parses an input into postfix notation and then evaluates the expression. It works for +,-,*,/, and ^, but I cannot get the unary - to work. Currently I am just trying to get the unary - to work at the start of an expression. I am using -5+2 to test the algorithm. The return result should be -3, however, I the program is returning -2. I have marked the 2 places in my code that I am trying to handle the unary - sign as

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

I have been debugging all day and cannot figure out what is not working. Here is my code:

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(&quot;Type and equation, then press enter: &quot;);
String g = f.nextLine();
test = inputToArrayList(g);
for (int z = 0; z &lt; 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&lt;Double&gt; operandStack = new Stack&lt;Double&gt;();
private static final Stack&lt;String&gt; operatorStack = new Stack&lt;String&gt;();
private static final String OPERATORS = &quot;+-/*%^()u&quot;;
private static final String NONBRACES = &quot;+-/*%^u&quot;;
private static final int[] PRECEDENCE = {1, 1, 2, 2, 2, 3, 3, 3, 4};
static ArrayList&lt;String&gt; charList = new ArrayList&lt;String&gt;();
public static ArrayList inputToArrayList(String input) {
StringBuilder strBuild = new StringBuilder();
String infix = input.replace(&quot; &quot;, &quot;&quot;);
try {
for (int i = 0; i &lt; infix.length(); i++) {
char c = infix.charAt(i);
boolean isNumber = (c &gt;= &#39;0&#39; &amp;&amp; c &lt;= &#39;9&#39;);

//------------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 == &#39;.&#39;) {
for (int j = 0; j &lt; strBuild.length(); j++) {
if (strBuild.charAt(j) == &#39;.&#39;) {
throw new SyntaxErrorException(&quot;You can&#39;t have two decimals in a number&quot;);
} 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(&quot;You can&#39;t end your equation with a decimal&quot;);
}
} 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(&quot;Make sure your input only contains numbers, operators, or parantheses&quot;);
}
}
int leftParenth = 0;
int rightParenth = 0;
for (int p = 0; p &lt; charList.size(); p++) {
String checkParenth = charList.get(p);
switch (checkParenth) {
case &quot;(&quot;:
leftParenth++;
break;
case &quot;)&quot;:
rightParenth++;
break;
default: //do nothing
break;
}
}
if (leftParenth != rightParenth) {
throw new SyntaxErrorException(&quot;There is not an even number of parenthesis&quot;);
}
int parenthesis = 0;
for (int f = 0; f &lt; charList.size(); f++) {
String awesome = charList.get(f);
switch (awesome) {
case &quot;(&quot;:
parenthesis++;
break;
case &quot;)&quot;:
parenthesis--;
break;
default:
break;
}
if (parenthesis &lt; 0) {
throw new SyntaxErrorException(&quot;Order of parenthesis is off&quot;);
}
}
if (NONBRACES.contains(charList.get(charList.size() - 1))) {
throw new SyntaxErrorException(&quot;The input can&#39;t end in an operator&quot;);
}
return charList;
} catch (SyntaxErrorException ex) {
System.out.println(ex);
return charList;
}
}
private static void processOperator(String op) {
if (operatorStack.empty() || op.equals(&quot;(&quot;)) {
operatorStack.push(op);
} else {
//peek the operator stack and
//let topOp be the top operator.
String topOp = operatorStack.peek();
if (precedence(op) &gt; precedence(topOp)) {
if (!op.equals(&quot;)&quot;)) {
operatorStack.push(op);
}
} else {
//Pop all stacked operators with equal
// or higher precedence than op.
while (!operatorStack.empty() &amp;&amp; precedence(op) &gt;= 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(&quot;(&quot;)) {
//matching &#39;(&#39; 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 &gt; top of stack operator precedence.
}
}
}
public static String calculateAnswer(ArrayList&lt;String&gt; infix) {
int p;
for (p = 0; p &lt; 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 (&quot;u&quot;.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 &quot;+&quot;:
operandStack.push(left + right);
break;
case &quot;-&quot;:
operandStack.push(left - right);
break;
case &quot;*&quot;:
operandStack.push(left * right);
break;
case &quot;/&quot;:
operandStack.push(left / right);
break;
case &quot;%&quot;:
operandStack.push(left % right);
break;
case &quot;^&quot;:
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)];
}

}

答案1

得分: 3

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

您需要存储附加状态，具体来说，是最后解析的元素类型以及是否处于“反转”状态。如果是运算符或无内容（即表达式的开头），那么“-”应该切换“反转”状态。数字应该检查并清除反转状态，如果必要的话，在添加到堆栈之前执行 *= -1。换句话说，这成为将一元运算符视为常数的一部分而不是运算符的一种处理方式。

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

还请注意，在这里的“正确”解决方案是当您的运算符不都是中缀时不要使用Shunting Yard算法。使用正确的语法解析器（例如Yacc）。

英文:

This is not a trivial problem to solve. Dijkstra's original algorithm was explicitly for infix operators and mentions (but doesn't solve) prefix or postfix operators. So there is no simple extension that universally handles unary operators.

You will need to store additional state; specifically, the last type of element parsed and whether you are in a 'inverse' state. If it's an operator or nothing (i.e. start of expression) then '-' should toggle the 'inverse' state. Numbers should check and clear the inverse state and *= -1 if necessary before adding to stack. In other words, this becomes a way of handling the unary operator as a part of the constant rather than as an operator.

Note those two paragraphs aren't contradictory! The solution above won't handle 3 * -(5 + 2) because it's not treating the '-' as an operator but, rather, a flag used when numbers are read.

Also note that the 'proper' solution here is to not use the shunting yard algorithm when your operators aren't all infix. Use a proper grammar parser (e.g. Yacc).

答案2

得分: 0

如果我们查看编程语言的优先级表格，请参阅运算符优先级（维基百科），我们会发现一元运算符与相应的中缀运算符具有不同的优先级级别。该表格通常如下：

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

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

我已经成功地遵循了递归下降解析表达式中的技术，这与逆波兰算法非常相似，但需要一些递归来处理括号。

我们可以将语法分为两部分：前缀-后缀表达式 P，其中包括数字、标识符、一元运算符（前缀和后缀）和括号表达式。完整表达式 E 是一堆由二元运算符分隔的 P。

P :: 数字
| 标识符，即变量名
| -P，前缀运算符后跟 P
| (E)，括号内的 E

表达式 E 将是

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

即一系列 P，其间由二元运算符分隔，比如 P+P+P-P。

对于部分 E，您可以使用逆波兰算法，但对于部分 P，需要一些递归。他的算法如下：

Eparser 是
var operators: Operator 的栈 := 空的
var operands: Tree 的栈 := 空的
push(operators, sentinel)
E(operators, operands)
expect(结束)
return top(operands)
E(operators, operands) 是
P(operators, operands)
当下一个是二元运算符时
pushOperator(二元(next)，operators，operands)
消耗
P(operators，operands)
当 top(operators) 不等于 sentinel 时
popOperator(operators，operands)
P(operators, operands) 是
如果下一个是 v
push(operands，mkLeaf(v))
消耗
否则如果下一个是 "（"
消耗
push(operators，sentinel)   -- 推入 sentinel
E(operators，operands)      -- 注意递归
expect(")")                 -- 从输入中移除括号
pop(operators)              -- 弹出 sentinel
否则如果下一个是一元运算符
pushOperator(一元(next)，operators，operands)
消耗
P(operators，operands)
否则
错误
popOperator(operators，operands) 是
如果 top(operators) 是二元的
const t1 := pop(operands)
const t0 := pop(operands)
push(operands，mkNode(pop(operators)，t0，t1))
否则
push(operands，mkNode(pop(operators)，pop(operands)))
pushOperator(op，operators，operands) 是
当 top(operators) > op 时
popOperator(operators，operands)
push(op，operators)

注意，当遇到开括号时，存在一个递归步骤。首先，将 sentinel 推入运算符栈，这是一些特殊的运算符，用于防止弹出太多运算符。然后代码再次调用 E。E 将运行直到发现闭括号。当 E 结束时，所有从栈中弹出直到第一个 sentinel 的运算符。

英文:

If we look at the precedence tables of programming languages see Order of Operations (Wikipedia) we see that the unary operators have a different precedence level to the corresponding infix operator. The table generally looks like

  1. () brackets
  2. +-! unary operators
  3. */ multiply and divide
  4. +- infix addition and subtraction
  5. == comparision operators
  6. = assignment operators

so your program needs a way of distinguishing between unary and binary operators with the same symbol. In Dijkstra work he gives unary minus the same precedence as * and /, but does not address how the parser distinguishes unary and binary cases.

I've successfully followed the technique in Parsing Expressions by Recursive Descent this is very similar to the shunting yard algorithm, but with a bit of recursion to handle the brackets.

We can divide our syntax into two parts: prefix-suffix expressions, P, which includes numbers, identified, unary operators (both as prefix and as suffixes), and bracketed expressions. Full expressions, E, are a bunch of P's separated by binary operators.

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

The expression E will be

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

i.e. a sequence of P's with binary operators between them say P+P+P-P.

For the E part you use a shunting yard but for P there is a bit of recursion. His algorithm is

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 = &quot;(&quot;
consume
push( operators, sentinel )   -- pushes sentinel
E( operators, operands )      -- note recursion
expect( &quot;)&quot; )                 -- 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) &gt; op
popOperator( operators, operands )
push( op, operators )

Note there is a recursive step when an open brackets is encountered. First sentinel is pushed onto the operator stack, this is some special operator used to prevent too many operators being poped. The code then calls E again. E will run until the closing brace is discovered. When E ends all the operators up to the first sentinel are popped from the stack.

huangapple
  • 本文由 发表于 2020年10月22日 10:30:22
  • 转载请务必保留本文链接：https://go.coder-hub.com/64474388.html
  • java
  • shunting-yard
  • stack
  • unary-operator
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定