后缀表达式栈计算器

Question

我为我的Java课程创建了一个堆栈计算器，用于解决类似以下的方程：

2 + ( 2 * ( 10 – 4 ) / ( ( 4 * 2 / ( 3 + 4) ) + 2 ) – 9 )
2 + { 2 * ( 10 – 4 ) / [ { 4 * 2 / ( 3 + 4) } + 2 ] – 9 }

我们需要在代码中实现{ } [ ]。我用括号( )实现了它，只用括号的方式完全有效。但是当我尝试添加{ } [ ]时，出现了问题。

目前为止，我的代码如下：

package stackscalc;

import java.util.Scanner;
import java.util.Stack;
import java.util.EmptyStackException;


class Arithmetic {
    int length;
    Stack stk;
    String exp, postfix;

    Arithmetic(String s) {
        stk = new Stack();
        exp = s;
        postfix = "";
        length = exp.length();

    }
    boolean isBalance() {
        boolean fail = false;
        int index = 0;

        try {
            while (index < length) {
                char ch = exp.charAt(index);

                switch(ch) {
                case ')':
                    stk.pop();
                    break;

                case '(':
                    stk.push(new Character(ch));
                    break;

                default:
                    break;
                }
                index++;
            }
        } catch (EmptyStackException e) {
            fail = true;
        }
        return stk.empty() && !fail;
    }
    void postfixExpression() {
        String token = "";
        Scanner scan = new Scanner(exp);
        stk.clear();

        while(scan.hasNext()) {
            token = scan.next();
            char current = token.charAt(0);

            if (isNumber(token)) {
                postfix = postfix + token + " ";
            } else if(isParentheses(current)) {
                if (current == '(') {
                    stk.push(current);
                } else {
                    Character ch = (Character) stk.peek();
                    char nextToken = ch.charValue();

                    while(nextToken != '(') {
                        postfix = postfix + stk.pop() + " ";

                        ch = (Character) stk.peek();

                        nextToken = ch.charValue();
                    }
                    stk.pop();
                }
            } else {
                if (stk.empty()) {
                    stk.push(current);
                } else {
                    Character ch = (Character) stk.peek();
                    char top = ch.charValue();

                    if (hasHigherPrecedence(top, current)) {
                        stk.push(current);
                    } else {
                        ch = (Character) stk.pop();

                        top = ch.charValue();

                        stk.push(current);

                        stk.push(top);
                    }
                }
            }
        }
        try {
            Character ch = (Character) stk.peek();
            char nextToken = ch.charValue();

            while (isOperator(nextToken)) {
                postfix = postfix + stk.pop() + " ";
                ch = (Character) stk.peek();
                nextToken = ch.charValue();
            }
        } catch (EmptyStackException e) {}
    }
    boolean isNumber(String s) {
        try {
            int Num = Integer.parseInt(s);
        } catch(NumberFormatException e) {
            return false;
        }
        return true;
    }
    void evaluateRPN() {
        Scanner scan = new Scanner(postfix);
        String token = "";
        stk.clear();

        while(scan.hasNext()) {
            try {
                token = scan.next();
                if (isNumber(token)) {
                    stk.push(token);
                } else {
                    char current = token.charAt(0);
                    double t1 = Double.parseDouble(stk.pop().toString());
                    double t2 = Double.parseDouble(stk.pop().toString());
                    double t3 = 0;

                    switch (current) {
                    case '+': {
                        t3 = t2 + t1;
                        stk.push(t3);
                        break;
                    }
                    case '-': {
                        t3 = t2 - t1;
                        stk.push(t3);
                        break;
                    }
                    case '*': {
                        t3 = t2 * t1;
                        stk.push(t3);
                        break;
                    }
                    case '/': {
                        t3 = t2 / t1;
                        stk.push(t3);
                        break;
                    }
                    default: {
                        System.out.println("Reverse Polish Notation was unable to be preformed.");
                    }
                }
            }

        } catch (EmptyStackException e) {}
    }
}
String getResult() {
    return stk.toString();
}

int stackSize() {
    return stk.size();
}

boolean isParentheses(char current) {
    if ((current == '(') || (current == ')')) {
        return true;
    } else {
        return false;
    }
}

boolean isOperator(char ch) {
    if ((ch == '-')) {
        return true;
    } else if ((ch == '+')) {
        return true;
    }
    else if ((ch == '*')) {
        return true;
    }
    else if((ch == '/')) {
        return true;
    } else {

    }
    return false;
}

boolean hasHigherPrecedence(char top, char current) {
    boolean HigherPre = false;

    switch (current) {
    case '*':
        HigherPre = true;
    break;

    case '/':
        HigherPre = true;
    break;

    case '+':

        if ((top == '*') || (top == '/') || (top == '-')) {
             HigherPre = false;
        } else {
             HigherPre = true;
        }

        break;

    case '-':
        if ((top == '*') || (top == '/') || (top == '-')) {
            HigherPre = false;
        } else {
            HigherPre = true;
        }
        break;

    default:
        System.out.println("Higher Precedence Unsuccessful was unable to be preformed.");
        break;
    }

    return HigherPre;


   }

    String getPostfix() {
        return postfix;
    }
}

- user1444775

---

你应该添加{}[]来做什么？ - user207421

Answer 1

我所假设的是，（），{}和[]在操作顺序方面具有相同的权重，您只需要修改代码以允许所有三个可互换使用。

如果是这种情况，我会使用匹配器类进行简单的正则表达式检查，以查看您正在查看的当前字符是否为括号、花括号或方括号。

    //convert char to string
    String temp += currentChar;
    //this will check for (, [, and { (need escapes because of how regex works in java)
    Pattern bracePattern = Pattern.compile("[\(\{\[]");
    Matcher matcher = numPatt.matcher(temp);
    if(matcher.find()){
    //you know you have a grouping character
    }

这段代码应该可以让你找到所有的开放分组字符（只需在正则表达式中将 (、{ 和 [ 替换为 )、} 和 ] 即可找到关闭字符）。 这可以在 isParenthesis() 方法中使用。

- namenamename

---

你还需要更新像 if(current == '(') 和 while(nextToken != '(') 这样的行。你的 isParenthesis() 也检查了右括号，所以确保你不要只是尝试复制/粘贴这个答案 =P - Windle

好的，明白了。我之前说的正则表达式检查可以使用的地方有点模糊。 - namenamename

你不想处理(2+3}，对吧？ - user3458

Answer 2

你可以使用类似这样的方法来简化检查是否匹配了'(', '[', 或 '{'的过程。

static char getExpected(char val){
       char expected=' ';
        switch (val) {
            case '(':
                expected=')';
                break;
            case '[':
                expected=']';
                break;
            case '{':
                expected='}';
                break;
        }
       return expected;
   }

- Pat H.