private Scanner sc = new Scanner(System.in);
private String expression;
private String exp[];
private ArrayList<String> post_fix = new ArrayList<>();
Stack<String> ope = new Stack<String>();
public Model()
{
expression = sc.nextLine();
}
public void split()
{
//splitting the entered expression to array of operators alone and array of the numbers then create Arraylist to combine the operators and numbers together as if it is a string expression but as an array
String num[]= this.expression.split("[/ /*/-]");
String preop[]= this.expression.split("[0-9] ");; // this will give [empty, operator, operator...] therefore we will create another array to fill in the ops excluding empty
ArrayList<String> op = new ArrayList<>();//I used arraylist because easier
for(int i = 1; i<preop.length;i )
{
op.add(preop[i]);
}
//putting the operands and the operators together in the same array
ArrayList<String> exp = new ArrayList<>();
for(int i = 0; i <num.length;i )
{
exp.add(num[i]);
}
int count = 0;
for(int i = 0; i <op.size();i )
{ //fill the arraylist with numbers then add the operators to it by using number (index of the operator 1 count)
exp.add(i 1 count, op.get(i)); //This is why arraylist was used in order to let values to be placed in between
count ;
//i 1 count is used because index of the operator is in between two numbers meaning it is after the first index in num array so i 1 and because array keeps increasing, we do count for the other operators to be placed in
}
this.exp = new String[exp.size()]; // we change the arraylist exp to instance array for faster operations later on
System.out.print("Test to check if expression is converted into array as intented: ");
for(int i = 0; i<this.exp.length;i )
{
this.exp[i] = exp.get(i);
System.out.print(this.exp[i]);
}
System.out.println();
}
public void postfix()
{
for(int i = 0; i < exp.length; i )
{
if(i%2 == 0)//since operands are observed to always have even index in the array
{
post_fix.add(exp[i]);
System.out.println(post_fix);
}
else
{
boolean x = !ope.empty();
System.out.println("Test of !ope.empty: " x);
while(!ope.empty()&& HasHigherPrecedence(ope.peek(), this.exp[i]))
{
post_fix.add(ope.peek());
ope.pop();
}
ope.push(exp[i]);
System.out.println("stack_top: " ope.peek());
}
}
while(!ope.empty())
{
post_fix.add(ope.peek());
ope.pop();
}
System.out.println("Output: " post_fix);
}
public String getPost_fix()
{
String temp = "";
for(int i =0; i < exp.length;i )
{
temp = temp post_fix.get(i);
}
return temp;
}
public double evaluate()
{
return 0;
}
private boolean HasHigherPrecedence(String op1, String op2)
{
//op1 is operator 1 at the top of the stack thus associativity highest
int a_op1 = 1;
int a_op2 = 0;
int p_op1 = 0;
int p_op2= 0;
//the precedence will be measured with numbers
String operators[]= {""," ","-","*","/"};
int precedence[] = {0,1,1,2,2}; //the reason for blank operator and 0 precedence is because the stack initially will be empty
for(int i = 0; i< operators.length;i )
{
if(op1.equals(operators[i]))
{
p_op1=precedence[i];
}
}
for(int i = 0; i< operators.length;i )
{
if(op2.equals(operators[i]))
{
p_op2=precedence[i];
}
}
boolean higher_ornot = false;
if(p_op1 > p_op2)
{
higher_ornot = false;
}
else if(p_op1 < p_op1)
{
higher_ornot = true;
}
else if(p_op1== p_op2)
{
System.out.println(op1 ": " p_op1);
System.out.println(op2 ": " p_op2);
higher_ornot = false; //since associativity of op1 will be higher --> thus higher precedence
}
return higher_ornot;
}
}
I am trying to converst user's infix mathmatical expression into a postfix expression in an array that will be evaluated but before evaluation, I faced a problem in the postfix method
while(!ope.empty()&& HasHigherPrecedence(ope.peek(), this.exp[i]))
This specific line is not being called out when the condition should be true, when it is comparing top of the stack which is * to - and * has higher precedence and since stack is not empty thus it should return true thus the function is called. I tested if I have any errors other areas but everything I tested was correct, I really have no clue how to fix.
I am really clueless even after 1hour and a half staring and trying to trace the code
I am expecting from output to be [3, 2, 4, *, , 3, -] which is the postfix expression that technically will be evaluated later
CodePudding user response：
I started by simplifying the code. You can use a map to store operator precedence:
private static final Map<String,Integer> PRECEDENCE = new HashMap<>();
static {
PRECEDENCE.put(" ", 1);
PRECEDENCE.put("-", 1);
PRECEDENCE.put("*", 2);
PRECEDENCE.put("/", 2);
}
This allows you to test if a string is a valid operator:
private static boolean isOperator(String s) {
return PRECEDENCE.containsKey(s);
}
as well as comparing the precedence of two operators:
private static boolean hasHigherPrecedence(String op1, String op2) {
return PRECEDENCE.get(op1) > PRECEDENCE.get(op2);
}
Instead of the complicated splits and loops at the begining, I would just parse the input expression while doing the postfix conversion. I need a variable pos to hold the current position, and methods readOperand and readOperator:
private int pos;
/* ... */
private String readOperand() {
int mark = pos;
while (pos < expression.length() && Character.isDigit(expression.charAt(pos))) {
pos;
}
return pos > mark ? expression.substring(mark, pos) : null;
}
private String readOperator() {
if (pos < expression.length() && isOperator(expression.substring(pos, pos 1))) {
return expression.substring(pos, pos);
}
return null;
}
The postfix method becomes:
public void postfix() {
String operand = readOperand();
while (operand != null) {
postfix.add(operand);
String op = readOperator();
if (op == null) {
break;
}
while (!ope.isEmpty() && !hasHigherPrecedence(op, ope.peek())) {
postfix.add(ope.pop());
}
ope.add(op);
operand = readOperand();
}
while (!ope.empty()) {
postfix.add(ope.pop());
}
System.out.println("Output: " postfix);
}
Note that
!hasHigherPrecedence(op, ope.peek())
is equivalent to:
PRECEDENCE.get(ope.peek()) >= PRECEDENCE.get(op)
so the operator at the top of the stack will be moved to the postfix array if its precedence is greater or equal to the precedence of the current operator.
CodePudding user response：
the reason is that the second condition HasHigherPrecedence is false in all cases, so even if the stack is non empty the whole condition is evaluated to false