所以任务是创造我们自己的解析器的表达式计算器。 例如:
输入:3 + 2 * 1-6 / 3输出:3
输入:3 ++ 2输出:无效表达
输入:-5 + 2输出:-3
输入:5--2输出:7
这里的代码解决了,除了它有一个固定的输入负值不能得到解决问题的一部分,我不是很确定但如果它确实解决运算符优先级的表达式。 但我已经修改了它获取用户输入表达式。 我一直在想了好几个小时如何实现负值的解决。 帮助任何人吗?
NO JavaScript引擎PLEASE。
这里是当前的代码
import java.util.*;
public class ExpressionParser
{
// Associativity constants for operators
private static final int LEFT_ASSOC = 0;
private static final int RIGHT_ASSOC = 1;
// Operators
private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();
static
{
// Map<"token", []{precendence, associativity}>
OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });
OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });
OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });
OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });
}
// Test if token is an operator
private static boolean isOperator(String token)
{
return OPERATORS.containsKey(token);
}
// Test associativity of operator token
private static boolean isAssociative(String token, int type)
{
if (!isOperator(token))
{
throw new IllegalArgumentException("Invalid token: " + token);
}
if (OPERATORS.get(token)[1] == type) {
return true;
}
return false;
}
// Compare precedence of operators.
private static final int cmpPrecedence(String token1, String token2)
{
if (!isOperator(token1) || !isOperator(token2))
{
throw new IllegalArgumentException("Invalid tokens: " + token1
+ " " + token2);
}
return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];
}
// Convert infix expression format into reverse Polish notation
public static String[] expToRPN(String[] inputTokens)
{
ArrayList<String> out = new ArrayList<String>();
Stack<String> stack = new Stack<String>();
// For each token
for (String token : inputTokens)
{
// If token is an operator
if (isOperator(token))
{
// While stack not empty AND stack top element
// is an operator
while (!stack.empty() && isOperator(stack.peek()))
{
if ((isAssociative(token, LEFT_ASSOC) &&
cmpPrecedence(token, stack.peek()) <= 0) ||
(isAssociative(token, RIGHT_ASSOC) &&
cmpPrecedence(token, stack.peek()) < 0))
{
out.add(stack.pop());
continue;
}
break;
}
// Push the new operator on the stack
stack.push(token);
}
// If token is a left bracket '('
else if (token.equals("("))
{
stack.push(token); //
}
// If token is a right bracket ')'
else if (token.equals(")"))
{
while (!stack.empty() && !stack.peek().equals("("))
{
out.add(stack.pop());
}
stack.pop();
}
// If token is a number
else
{
// if(!isOperator(stack.peek())){
// out.add(String.valueOf(token*10));
// }
out.add(token);
}
}
while (!stack.empty())
{
out.add(stack.pop());
}
String[] output = new String[out.size()];
return out.toArray(output);
}
public static double RPNtoDouble(String[] tokens)
{
Stack<String> stack = new Stack<String>();
// For each token
for (String token : tokens) //for each
{
// If the token is a value push it onto the stack
if (!isOperator(token))
{
stack.push(token);
}
else
{
// Token is an operator: pop top two entries
Double d2 = Double.valueOf( stack.pop() );
Double d1 = Double.valueOf( stack.pop() );
//Get the result
Double result = token.compareTo("*") == 0 ? d1 * d2 :
token.compareTo("/") == 0 ? d1 / d2 :
token.compareTo("+") == 0 ? d1 + d2 :
d1 - d2;
// Push result onto stack
stack.push( String.valueOf( result ));
}
}
return Double.valueOf(stack.pop());
}
public static void main(String[] args) throws Exception{
Scanner in = new Scanner(System.in);
String reg = "((?<=[<=|>=|==|\\+|\\*|\\-|<|>|/|=])|(?=[<=|>=|==|\\+|\\*|\\-|<|>|/|=]))";
while(true){
try{
System.out.println("Enter Your Expression");
//String[] input = "( 1 + 2 ) * ( 3 / 4 ) - ( 5 + 6 )".split(" ");
String[] input = in.nextLine() .split(reg);
String[] output = expToRPN(input);
// Build output RPN string minus the commas
System.out.print("Stack: ");
for (String token : output) {
System.out.print("[ ");System.out.print(token + " "); System.out.print("]");
}
System.out.println(" ");
// Feed the RPN string to RPNtoDouble to give result
Double result = RPNtoDouble( output );
System.out.println("Answer= " + result);
}catch (NumberFormatException | EmptyStackException nfe){
System.out.println("INVALID EXPRESSION"); }
}
}
}
更新后的代码:补充:unaryToexp()函数。 我想要做的是,每次一个“ - ”时,代码通过改变它把它作为一个二进制“_”作为另一家运营商和该运营商-1解决乘法的事情(我想要的东西首先是添加[ - 1]和[*]至RPN栈)。 仍然有问题在这里。
编译器说:
Enter Your Expression
-5+3
Stack: [ ][ 5 ][ - ][ 3 ][ + ]
Exception in thread "main" java.lang.NumberFormatException: empty String
at sun.misc.FloatingDecimal.readJavaFormatString(FloatingDecimal.java:10 11)
at java.lang.Double.valueOf(Double.java:504)
at ExpressionParser.RPNtoDouble(ExpressionParser.java:160)
at ExpressionParser.main(ExpressionParser.java:194)*
我认为这事做的Double d1 = Double.valueOf( stack.pop() );
导致它仍然弹出另外两个值,在这里我只需要一个用于求解一元运算符。 任何帮助吗?
public class ExpressionParser
{
// Associativity constants for operators
private static final int LEFT_ASSOC = 0;
private static final int RIGHT_ASSOC = 1;
// Operators
private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();
static
{
// Map<"token", []{precendence, associativity}>
OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });
OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });
OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });
OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });
OPERATORS.put("_", new int[] { 5, RIGHT_ASSOC });
}
// Test if token is an operator
private static boolean isOperator(String token)
{
return OPERATORS.containsKey(token);
}
// Test associativity of operator token
private static boolean isAssociative(String token, int type)
{
if (!isOperator(token))
{
throw new IllegalArgumentException("Invalid token: " + token);
}
if (OPERATORS.get(token)[1] == type) {
return true;
}
return false;
}
// Compare precedence of operators.
private static final int cmpPrecedence(String token1, String token2)
{
if (!isOperator(token1) || !isOperator(token2))
{
throw new IllegalArgumentException("Invalid tokens: " + token1
+ " " + token2);
}
return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];
}
// CONVERT UNARY OPERATORS
public static String[] unaryToexp(String[] inputTokens)
{
ArrayList<String> out = new ArrayList<String>();
Stack<String> stack = new Stack<String>();
//if token is an unary minus
for (String token : inputTokens)
{
if( ((token == "-") && (isOperator(stack.peek()) || stack.empty() ))){ //
token = "_";
}
else if (token == "-"){
token = "-";
}
out.add(token);
while (!stack.empty())
{
out.add(stack.pop());
}
}
String[] output = new String[out.size()];
return out.toArray(output);
}
// Convert infix expression format into reverse Polish notation
public static String[] expToRPN(String[] inputTokens)
{
ArrayList<String> out = new ArrayList<String>();
Stack<String> stack = new Stack<String>();
// For each token
for (String token : inputTokens)
{
// If token is an operator
if (isOperator(token))
{
// While stack not empty AND stack top element
// is an operator
while (!stack.empty() && isOperator(stack.peek()))
{
if ((isAssociative(token, LEFT_ASSOC) &&
cmpPrecedence(token, stack.peek()) <= 0) ||
(isAssociative(token, RIGHT_ASSOC) &&
cmpPrecedence(token, stack.peek()) < 0))
{
out.add(stack.pop());
continue;
}
break;
}
// Push the new operator on the stack
stack.push(token);
}
// If token is a left bracket '('
else if (token.equals("("))
{
stack.push(token); //
}
// If token is a right bracket ')'
else if (token.equals(")"))
{
while (!stack.empty() && !stack.peek().equals("("))
{
out.add(stack.pop());
}
stack.pop();
}
// If token is a number
else
{
out.add(token);
}
}
while (!stack.empty())
{
out.add(stack.pop());
}
String[] output = new String[out.size()];
return out.toArray(output);
}
public static double RPNtoDouble(String[] tokens)
{
Stack<String> stack = new Stack<String>();
// For each token
for (String token : tokens)
{
// If the token is a value push it onto the stack
if (!isOperator(token))
{
stack.push(token);
}
else
{
// Token is an operator: pop top two entries
Double d2 = Double.valueOf( stack.pop() );
Double d1 = Double.valueOf( stack.pop() );
//Get the result
Double result = token.compareTo("_") == 0 ? d2 * -1 :
token.compareTo("*") == 0 ? d1 * d2 :
token.compareTo("/") == 0 ? d1 / d2 :
token.compareTo("+") == 0 ? d1 + d2 :
d1 - d2;
// Push result onto stack
stack.push( String.valueOf( result ));
}
}
return Double.valueOf(stack.pop());
}
public static void main(String[] args) throws Exception{
Scanner in = new Scanner(System.in);
String reg = "((?<=[<=|>=|==|\\+|\\*|\\-|\\_|<|>|/|=])|(?=[<=|>=|==|\\+|\\*|\\-|<|>|/|=]))";
while(true){
//try{
System.out.println("Enter Your Expression");
//String[] input = "( 1 + 2 ) * ( 3 / 4 ) - ( 5 + 6 )".split(" ");
String[] input = in.nextLine() .split(reg);
String[] unary = unaryToexp(input); //.split(reg);
String[] output = expToRPN(unary);
// Build output RPN string minus the commas
System.out.print("Stack: ");
for (String token : output) {
System.out.print("[ ");System.out.print(token); System.out.print(" ]");
}
System.out.println(" ");
// Feed the RPN string to RPNtoDouble to give result
Double result = RPNtoDouble( output );
System.out.println("Answer= " + result);
//}catch (){
//System.out.println("INVALID EXPRESSION"); }
}
}
}