Question

Please use the JAVA code attached as an input to the program that must be created IN JAVA.

Instructions of the program:

Write a non-recursive program using a stack that evaluates arithmetic expressions over the set Zs= 10, 1, 2). Assume that the expressions consist of operands from Zs only, parentheses, and three operations,田3, 3 and 3, which represent the common arithmetic operations +,-, * modular 3, in that order. For examples, 2 3 1-(2 + 1) mod 3 0 and 1 Θ3 2 2 (1-2 * 2) mod 3 = 0. Note that like regular arithmetic operations + and-, the first operands of operations 3 and G, can be omitted if they are 0's appearing as the first tokens of an expression or right after a "(". For examples, 3 2-(2) mod 3-1. 2 3 (3 1) (2 (-1)) mod 3- 1, and 31+1 mod 3 1. Analyze the running time of your algorithm in terms of the input size n, which in this case is the number of symbols in the logical expression given as the input. Run your program on 3 randomly generated arithmetic expression over containing at least 100, 1000 and 10000 symbols to verify your running time analysis result. Z3. Feel free to use common symbols +,-and * to represent O3 and in that order, for the easiness of programming. You should also assume the following operator precedence: (), 3, 3, and θ3, where 3, and θ3 are considered having the same priorities. Note: We now allow 3 and 3 to be "unary" serving as the sign symbol if they are the first operations of an expression or immediately after a (".So you need to think about what modifications need to be made on the stack-based algorithm for evaluating expressions in order to correctly handle expressions containing unary 3 and Эз . You may use the following attached programs to randomly generate arithmetic expressions over Zs and test cases to verify the correctness of your program: Program for generating random arithmetic expressions o - See attached. Test cases (all operations are modular 3): -+2-1+0*0+0+(+(0*0+2)) value: 0 ((1*0)*(0+(+1+2)*1) value: 0 +0*1+(1*0)-2*0+0*1-2-(0)*(2*0+(1)-1)-0+0 0-((2-2) value: 1 (1)+1+2+(0-1+2-(+(2-0+(1-1)*1+2)*2+2*2-2+2-0))+0+2 value: 1

java code:

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *

 */

import java.util.Random;

public class Rand_Z3_Exp {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
        int m = 100;
        
        System.out.println(rand_gen_z3Exp(m));
        
        System.exit(0);
}
    
   
    public static String rand_gen_z3Exp (int n){
        
        if (n<=0)
            return "";
        
        //possible symbols in the expression
        String symbols = "012(+-*)";
        //possible symbols after each current symbol
        String[] succ = {"*+-)","*+-)", "*+-)", "012(+-", "012(", "012(", "012(", ")+-*"};
        //Ouput string initialized;
        String z3_exp = "";
        
        //number of left apparantheses generated so far
        int num_of_lp = 0;
        //randomly generate first symbol in the output
        Random r = new Random();        
        int symbol_no = r.nextInt(6);
        char first_symbol = symbols.charAt(symbol_no);
        if (symbol_no == 3)
            num_of_lp++; 
        z3_exp += first_symbol;
        
        // The last symbol generated
        char last_symbol = first_symbol;
        // The main loop that generates the rest of the expression
        for(int i=1; i<n-num_of_lp; i++){
            
            String s = succ[symbols.indexOf(last_symbol)]; 

            // genrating the next symbol in the expression and
            // make sure that it conforms to format of loogical expressions
            char next_symbol;
            boolean again;
            do{
                again = false;
                next_symbol = s.charAt(r.nextInt(s.length()));
                switch (next_symbol){
                    case ')':   // All parantheses seen so far matched
                                // ) is not allowed for next symbol
                                if (num_of_lp==0){ 
                                    again = true;
                                }
                                else
                                    num_of_lp--;
                                break;
                    case '(':   num_of_lp++; 
                                break;
                    default:
                }
            
            }while(again);
            
            z3_exp += next_symbol;
            last_symbol = next_symbol;
        }
        
        // check if the last symbol is an operator or '(' and hence need an operand to complete the expression
        if (last_symbol=='(' ||  last_symbol=='*' ||  last_symbol=='+' ||  last_symbol=='-')        
            z3_exp += symbols.charAt(r.nextInt(3));
        
        // adding necessary closing )'s
        for(int i=0; i<num_of_lp; i++)
            z3_exp += ')';
        
        /* removing unneeded parentheses of the form "(z)" where z = 0, 1 , or 2.
        for(int i=0; i<3; i++)
            z3_exp = z3_exp.replace("("+i+")", String.valueOf(i));*/
        
        return z3_exp;
    }

}

Answer 1

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/

import java.util.Random;

import java.util.Stack;

public class RandZ3Exp {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
  
int m = 100;
String exp = rand_gen_z3Exp(m);
System.out.println(exp);
  
System.out.println(evaluate(exp));
  
System.exit(0);
}
public static boolean hasPrecedence(char op1, char op2)
{
if (op2 == '(' || op2 == ')')
return false;
if ((op1 == '*' ) && (op2 == '+' || op2 == '-'))
return false;
else
return true;
}
  
// A utility method to apply an operator 'op' on operands 'a'
// and 'b'. Return the result.
public static int applyOp(char op, int b, int a)
{
switch (op)
{
case '+':
return (a + b) % 3;
case '-':
return (a - b)%3;
case '*':
return (a * b)%3;
}
return 0;
}
  
public static int evaluate(String expression)
{
char[] tokens = expression.toCharArray();
  
// Stack for numbers: 'values'
Stack<Integer> values = new Stack<Integer>();
  
// Stack for Operators: 'ops'
Stack<Character> ops = new Stack<Character>();
  
for (int i = 0; i < tokens.length; i++)
{
// Current token is a whitespace, skip it
if (tokens[i] == ' ')
continue;
  
// Current token is a number, push it to stack for numbers
if (tokens[i] >= '0' && tokens[i] <= '9')
{
StringBuffer sbuf = new StringBuffer();
// There may be more than one digits in number
while (i < tokens.length && tokens[i] >= '0' && tokens[i] <= '9')
sbuf.append(tokens[i++]);
values.push(Integer.parseInt(sbuf.toString()));
}
  
// Current token is an opening brace, push it to 'ops'
else if (tokens[i] == '(')
ops.push(tokens[i]);
  
// Closing brace encountered, solve entire brace
else if (tokens[i] == ')')
{
while (ops.peek() != '(')
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
ops.pop();
}
  
// Current token is an operator.
else if (tokens[i] == '+' || tokens[i] == '-' ||
tokens[i] == '*')
{
// While top of 'ops' has same or greater precedence to current
// token, which is an operator. Apply operator on top of 'ops'
// to top two elements in values stack
while (!ops.empty() && hasPrecedence(tokens[i], ops.peek()))
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
  
// Push current token to 'ops'.
ops.push(tokens[i]);
}
}
  
// Entire expression has been parsed at this point, apply remaining
// ops to remaining values
while (!ops.empty())
values.push(applyOp(ops.pop(), values.pop(), values.pop()));
  
// Top of 'values' contains result, return it
return values.pop();
}

public static String rand_gen_z3Exp (int n){
  
if (n<=0)
return "";
  
//possible symbols in the expression
String symbols = "012(+-*)";
//possible symbols after each current symbol
String[] succ = {"*+-)","*+-)", "*+-)", "012(+-", "012(", "012(", "012(", ")+-*"};
//Ouput string initialized;
String z3_exp = "";
  
//number of left apparantheses generated so far
int num_of_lp = 0;
//randomly generate first symbol in the output
Random r = new Random();
int symbol_no = r.nextInt(6);
char first_symbol = symbols.charAt(symbol_no);
if (symbol_no == 3)
num_of_lp++;
z3_exp += first_symbol;
  
// The last symbol generated
char last_symbol = first_symbol;
// The main loop that generates the rest of the expression
for(int i=1; i<n-num_of_lp; i++){
  
String s = succ[symbols.indexOf(last_symbol)];

// genrating the next symbol in the expression and
// make sure that it conforms to format of loogical expressions
char next_symbol;
boolean again;
do{
again = false;
next_symbol = s.charAt(r.nextInt(s.length()));
switch (next_symbol){
case ')': // All parantheses seen so far matched
// ) is not allowed for next symbol
if (num_of_lp==0){
again = true;
}
else
num_of_lp--;
break;
case '(': num_of_lp++;
break;
default:
}
  
}while(again);
  
z3_exp += next_symbol;
last_symbol = next_symbol;
}
  
// check if the last symbol is an operator or '(' and hence need an operand to complete the expression
if (last_symbol=='(' || last_symbol=='*' || last_symbol=='+' || last_symbol=='-')
z3_exp += symbols.charAt(r.nextInt(3));
  
// adding necessary closing )'s
for(int i=0; i<num_of_lp; i++)
z3_exp += ')';
  
/* removing unneeded parentheses of the form "(z)" where z = 0, 1 , or 2.
for(int i=0; i<3; i++)
z3_exp = z3_exp.replace("("+i+")", String.valueOf(i));*/
  
return z3_exp;
}

}

RandZ3Exp.java 3 20 To change this license header, choose License Headers in Project Properties. import java.util.Random; 9 import java.util.stack; 11 public class RandZ3Exp t 13 ** 15 16 public static void main(Stringl] args) am args the command line arguments int m - 100; String exp-rand gen z3Exp (m); System.out.println(exp); 19 21 23 System.out.println(evatuate(exp)); System. exit(0); 26 public static boolean hasPrecedence(char op1, char op2) 27 28 L Markers-Properties Snippets .-Problems 貝Console X terminated> Randz3Exp [Java Progress Search Debug lication] CProgram Files Vava jdk1.8.0_171rebin javaw.exe (Mar 30, 2019, 11:03:21