Вычисление арифметического выражения отрицательного числа через стек

Question

Мне нужна ваша помощь, чтобы рассчитать отрицательные числа. Я не мог считать отрицательные числа. Я не могу вычислить только положительные числа. Буду рад, если вы поможете мне исправить это.

Я хочу быть уверенным - сложность кода O (n)?

import java.util.Stack; 

public class Q2_M3 // O(N) 
{ 
    public static double Calculate(String st) 
    { 
     char[] Arr = st.toCharArray(); 
     Stack<Double> values = new Stack<Double>();// Stack for numbers: 
     Stack<Character> oper = new Stack<Character>();// Stack for Operators: 

    for (int i = 0; i < Arr.length; i++) 
    { 
     if (Arr[i] >= '0' && Arr[i] <= '9') 
     { 
      StringBuffer sbuf = new StringBuffer(); 
      while ((i < Arr.length) && ((Arr[i] >= '0' && Arr[i] <= '9')||(Arr[i] == '.')||(Arr[i] == '-'))) 
       sbuf.append(Arr[i++]); 
      values.push(Double.parseDouble(sbuf.toString())); 
      i--; 
     } 
     // Current token is an opening brace, push it to 'oper' 
     else if (Arr[i] == '(') 
      oper.push(Arr[i]); 

     // Closing brace encountered, solve entire brace 
     else if (Arr[i] == ')') 
     { 
      while (oper.peek() != '(') 
       values.push(doArithmetic(oper.pop(), values.pop(), values.pop())); 
      oper.pop(); 
     } 

     // Current token is an operator. 
     else if (Arr[i] == '+' || Arr[i] == '-' || 
       Arr[i] == '*' || Arr[i] == '/') 
     { 
      // While top of 'oper' has same or greater precedence to current 
      // token, which is an operator. Apply operator on top of 'oper' 
      // to top two elements in values stack 
      while (!oper.empty() && hasPrecedence(Arr[i], oper.peek())) 
       values.push(doArithmetic(oper.pop(), values.pop(), values.pop())); 
      oper.push(Arr[i]); 
     } 
    } 
    // Entire expression has been parsed at this point, apply remaining 
    // oper to remaining values 
    double val= 0; 
    while (!oper.empty()){ 
     if(!values.isEmpty()) 
     //values.push(doArithmetic(oper.pop(), values.pop(), values.pop())); 
     values.push(doArithmetic(oper.pop(), values.pop(), values.pop())); 
     val=values.peek(); 
    } 
    // Top of 'values' contains result, return it 
    return val; 
} 

// Returns true if 'op2' has higher or same precedence as 'op1', 
// otherwise returns false. 
public static boolean hasPrecedence(char op1, char op2) 
{ 
    if (op1 == '(' || op2 == '(') 
     return false; 
    if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) 
     return false; 
    else 
     return true; 
} 

public static double doArithmetic(char oper, Double x, Double y) 
{ 
    switch (oper) 
    { 
    case '+': 
     return y + x; 
    case '-': 
     return y - x; 
    case '*': 
     return y * x; 
    case '/': 
     if (x == 0) 
      System.out.println("Cannot divide by zero!"); 
     else 
     return y/x; 
    } 
    return 0; 
} 

public static void main(String[] args) 
{ 
    String st = "-5*(6+2)-12/4"; 
    String st2 = "20.2*(6.56567+2)-162/2"; 
    System.out.println(Calculate(st)); 
    System.out.println("Ans: "+Calculate(st2)); 

} 
} 

Answer 1

Во-первых

while ((i < Arr.length) && ((Arr[i] >= '0' && Arr[i] <= '9')||(Arr[i] == '.')||(Arr[i] == '-'))) 

только делает, так как ваше состояние выглядел как этот

if ((Arr[i] >= '0' && Arr[i] <= '9') || Arr[i] == '-') 

Единственное Изменился материал вправо.

Я также сменил начало функции для замены в любом месте - знаком +- за исключением начала.

import java.util.*; 
public class f { 
    public static double Calculate(String st) { 
     String pattern = "-"; 
     if (st.charAt(0)=='-') 
      st = '-'+st.substring(1).replaceAll(pattern, "+-"); 
     else 
      st = st.replaceAll(pattern, "+-"); 

     char[] Arr = st.toCharArray(); 
     Stack<Double> values = new Stack<>();// Stack for numbers: 
     Stack<Character> oper = new Stack<>();// Stack for Operators: 

     for (int i = 0; i < Arr.length; i++) { 
      if ((Arr[i] >= '0' && Arr[i] <= '9') || Arr[i] == '-') { 
       StringBuffer sbuf = new StringBuffer(); 
       while ((i < Arr.length) && ((Arr[i] >= '0' && Arr[i] <= '9')||(Arr[i] == '.')||(Arr[i] == '-'))) 
        sbuf.append(Arr[i++]); 
       values.push(Double.parseDouble(sbuf.toString())); 
       i--; 
      } 
      // Current token is an opening brace, push it to 'oper' 
      else if (Arr[i] == '(') 
       oper.push(Arr[i]); 

      // Closing brace encountered, solve entire brace 
      else if (Arr[i] == ')') { 
       while (oper.peek() != '(') 
        values.push(doArithmetic(oper.pop(), values.pop(), values.pop())); 
       oper.pop(); 
      } 

      // Current token is an operator. 
      else if (Arr[i] == '+' || Arr[i] == '-' || Arr[i] == '*' || Arr[i] == '/') { 
       // While top of 'oper' has same or greater precedence to current 
       // token, which is an operator. Apply operator on top of 'oper' 
       // to top two elements in values stack 
       while (!oper.empty() && hasPrecedence(Arr[i], oper.peek())) 
        values.push(doArithmetic(oper.pop(), values.pop(), values.pop())); 
       oper.push(Arr[i]); 
      } 
     } 
     // Entire expression has been parsed at this point, apply remaining 
     // oper to remaining values 
     double val= 0; 
     while (!oper.empty()){ 
      if(!values.isEmpty()) 
       //values.push(doArithmetic(oper.pop(), values.pop(), values.pop())); 
       values.push(doArithmetic(oper.pop(), values.pop(), values.pop())); 
      val=values.peek(); 
     } 
     // Top of 'values' contains result, return it 
     return val; 
    } 

    // Returns true if 'op2' has higher or same precedence as 'op1', 
    // otherwise returns false. 
    public static boolean hasPrecedence(char op1, char op2) { 
     if (op1 == '(' || op2 == '(') 
      return false; 
     if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) 
      return false; 
     else 
      return true; 
    } 

    public static double doArithmetic(char oper, Double x, Double y) { 
     switch (oper) { 
      case '+': 
       return y + x; 
      case '-': 
       return y - x; 
      case '*': 
       return y * x; 
      case '/': 
       if (x == 0) 
        System.out.println("Cannot divide by zero!"); 
       else 
        return y/x; 
     } 
     return 0; 
    } 

    public static void main(String[] args) { 
     String st = "-5*(6+2)-12/4"; 
     String st2 = "20.2*(6.56567+2)-162/2"; 
     System.out.println(Calculate(st)); 
     System.out.println("Ans: "+Calculate(st2)); 
    } 
} 

Не уверен, что это слишком медленно, но, похоже, оно работает для тестовых случаев в основном методе.

Answer 2

Так что вам действительно нужно различать двоичный оператор a-b и унарный оператор -c.

С точки зрения формальной грамматики, вы можете определить Expression нечто подобное с префиксом быть числом или - с последующим числом

Expression : 
    PrefixExpression 
    Expression BinaryOp Expression 
Prefix: 
    NumberOrVar 
    - NumberOrVar 
    (Expression) 
NumberOrVar: 
    0-9 
    a-z 

В коде это становится как

Expression() { 
    while(more tokens) { 
    Prefix(); 
    Char op = next input item, will be an operator 
    PushOperator(op) 
    Prefix() 
    } 

} 

Prefix() { 
    Char c = next input 
    if(c == '-') { 
      PushOperator(UnitaryMinus) 
      c = next input 
    } 
    if(c in 0-9) 
      values.push(c) 
}