Implement four operational codes in Java
- 2020-04-01 04:09:16
- OfStack
Recently, I searched the Internet and found that I could not find the code of four operations written in Java.
1.
The code just implemented the simple four operations, support +,-,*,/,(,) can only calculate the value of the correct expression, no illegal expression check.
2. Implementation method
Step 1: convert the input String to List, which is mainly used to convert strings to atoms: numeric/operator/parenthesis
public List transStr(String str)
{
List strList = new ArrayList();
String tmp = str.replaceAll("\d*", "");
String curLet = null;
int loc = 0;
int len = tmp.length();
for (int i = 0; i < len; i++)
{
curLet = tmp.substring(i, i + 1);
loc = str.indexOf(curLet);
if (!"".equals(str.substring(0, loc).trim()))
{
strList.add(str.substring(0, loc).trim());
}
strList.add(str.substring(loc, loc + 1));
str = str.substring(loc + 1);
}
if (0 < str.length())
{
strList.add(str.trim());
}
return strList;
}The second step: the original infix expression into the suffix expression, in the four operations, the suffix expression is the most convenient to calculate
public String[] midToEnd(List midList)
{
Stack embl = new Stack();
Stack result = new Stack();
Iterator it = midList.iterator();
String curStr = null;
while (it.hasNext())
{
curStr = (String) it.next();
if(sign.containsKey(curStr))
{
if (0 == embl.size() || "(".equals(curStr))
{
embl.push(curStr);
}
else
{
if(")".equals(curStr))
{
while(!"(".equals((String)embl.peek()))
{
if(0 >= embl.size())
{
return null;
}
result.push(embl.pop());
}
embl.pop();
}
else
{
int p1 = Integer.parseInt((String) sign.get(curStr));
int p2 = Integer.parseInt((String) sign.get(embl.peek()));
if (p1 > p2)
{
embl.push(curStr);
}
else
{
while (p1 <= p2 || embl.size() > 0)
{
result.push(embl.pop());
if(0 == embl.size())
{
break;
}
p2 = Integer.parseInt((String) sign.get(embl.peek()));
}
embl.push(curStr);
}
}
}
}
else
{
result.push(curStr);
}
}
while (0 < embl.size())
{
result.push(embl.pop());
}
int len = result.size();
String[] ret = new String[len];
for (int i = 0; i < len; i++)
{
ret[len - i - 1] = (String) result.pop();
}
return ret;
}Step 3: the postfix expression is parsed to return the final result of the calculation
public Object calculate(String[] endStr)
{
int len = endStr.length;
Stack calc = new Stack();
double p2;
double p1;
for (int i = 0; i < len; i++)
{
if (sign.containsKey(endStr[i]))
{
try
{
p2 = Double.parseDouble((String) calc.pop());
p1 = Double.parseDouble((String) calc.pop());
calc.push(String.valueOf(simpleCalc(p1, p2,endStr[i])));
}
catch(NumberFormatException ex)
{
ex.printStackTrace();
return "Input Error";
}
catch(Exception ex)
{
ex.printStackTrace();
return "Input Error";
}
}
else
{
calc.push(endStr[i]);
}
}
if (1 == calc.size())
{
return calc.pop();
}
else
{
return "Input Error";
}
}
/**
* Implement the underlying operation function
* @param double p1 digital 1
* @param double p1 digital 2
* @param String oper The operator +-
public double simpleCalc(double p1, double p2, String oper)
{
switch(oper.charAt(0))
{
case '+':
return p1 + p2;
case '-':
return p1 - p2;
case '*':
return p1 * p2;
case '/':
return p1 / p2;
default:
return p1;
}
}Step 4: the priority of the operator is extracted from the cache
private static HashMap sign = new HashMap();
public CalculateExp()
{
sign.put(")", "3");
sign.put("*", "2");
sign.put("/", "2");
sign.put("+", "1");
sign.put("-", "1");
sign.put("(", "0");
}The complete code
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
/**
* Java Implement the evaluation expression
* It only implements operations with addition, subtraction, multiplication and division and parentheses
* For example, : 3+12+25*(20-20/4)+10
* @author GuoBo 2009-3-16
* @version 1.0
*/
public class CalculateExp
{
private static HashMap sign = new HashMap();
public CalculateExp()
{
sign.put(")", "3");
sign.put("*", "2");
sign.put("/", "2");
sign.put("+", "1");
sign.put("-", "1");
sign.put("(", "0");
}
/**
* @param String Input expression
* @return List Parsed string element
* Parse the input string
* Convert to data that needs to be processed
* For example, :3+12+25*(20-20/4)+10
* The converted result is :
* List Elements for ret = {3,+,12,+,25,*,(,20,-,20,-,20,/,4,),+,10}
*/
public List transStr(String str)
{
List strList = new ArrayList();
String tmp = str.replaceAll("\d*", "");
String curLet = null;
int loc = 0;
int len = tmp.length();
for (int i = 0; i < len; i++)
{
curLet = tmp.substring(i, i + 1);
loc = str.indexOf(curLet);
if (!"".equals(str.substring(0, loc).trim()))
{
strList.add(str.substring(0, loc).trim());
}
strList.add(str.substring(loc, loc + 1));
str = str.substring(loc + 1);
}
if (0 < str.length())
{
strList.add(str.trim());
}
return strList;
}
public String[] midToEnd(List midList)
{
Stack embl = new Stack();
Stack result = new Stack();
Iterator it = midList.iterator();
String curStr = null;
while (it.hasNext())
{
curStr = (String) it.next();
if(sign.containsKey(curStr))
{
if (0 == embl.size() || "(".equals(curStr))
{
embl.push(curStr);
}
else
{
if(")".equals(curStr))
{
while(!"(".equals((String)embl.peek()))
{
if(0 >= embl.size())
{
return null;
}
result.push(embl.pop());
}
embl.pop();
}
else
{
int p1 = Integer.parseInt((String) sign.get(curStr));
int p2 = Integer.parseInt((String) sign.get(embl.peek()));
if (p1 > p2)
{
embl.push(curStr);
}
else
{
while (p1 <= p2 || embl.size() > 0)
{
result.push(embl.pop());
if(0 == embl.size())
{
break;
}
p2 = Integer.parseInt((String) sign.get(embl.peek()));
}
embl.push(curStr);
}
}
}
}
else
{
result.push(curStr);
}
}
while (0 < embl.size())
{
result.push(embl.pop());
}
int len = result.size();
String[] ret = new String[len];
for (int i = 0; i < len; i++)
{
ret[len - i - 1] = (String) result.pop();
}
return ret;
}
public Object calculate(String[] endStr)
{
int len = endStr.length;
Stack calc = new Stack();
double p2;
double p1;
for (int i = 0; i < len; i++)
{
if (sign.containsKey(endStr[i]))
{
try
{
p2 = Double.parseDouble((String) calc.pop());
p1 = Double.parseDouble((String) calc.pop());
calc.push(String.valueOf(simpleCalc(p1, p2,endStr[i])));
}
catch(NumberFormatException ex)
{
ex.printStackTrace();
return "Input Error";
}
catch(Exception ex)
{
ex.printStackTrace();
return "Input Error";
}
}
else
{
calc.push(endStr[i]);
}
}
if (1 == calc.size())
{
return calc.pop();
}
else
{
return "Input Error";
}
}
/**
* Implement the underlying operation function
* @param double p1 digital 1
* @param double p1 digital 2
* @param String oper The operator +-
public double simpleCalc(double p1, double p2, String oper)
{
switch(oper.charAt(0))
{
case '+':
return p1 + p2;
case '-':
return p1 - p2;
case '*':
return p1 * p2;
case '/':
return p1 / p2;
default:
return p1;
}
}
public static void main(String[] args)
{
CalculateExp ce = new CalculateExp();
String tmp = "3+12+25*(20-20/4+10";
String ret = (String) ce.calculate(ce.midToEnd(ce
.transStr(tmp)));
double value = 0;
try
{
value = Double.parseDouble(ret);
}
catch (NumberFormatException ex)
{
System.out.print(ret);
}
System.out.print(value);
}
}
The following is what other netizens have added
The idea of the code is to compute each of the smallest cells by regular judgment. Here's the code:
import java.math.BigDecimal;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class CalculatorUtil {
public static BigDecimal arithmetic(String exp){
if(!exp.matches("\d+")){
String result = parseExp(exp).replaceAll("[\[\]]", "");
return new BigDecimal(result);
}else{
return new BigDecimal(exp);
}
}
private static String minExp="^((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\]))[\+\-\*\/]((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\]))$";
private static String noParentheses="^[^\(\)]+$";
private static String priorOperatorExp="(((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\]))[\*\/]((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\])))";
private static String operatorExp="(((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\]))[\+\-]((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\])))";
private static String minParentheses="\([^\(\)]+\)";
/**
* Analytic calculation of the four operational expressions, example: 2+((3+4)*2-22)/2*3
* @param expression
* @return
*/
private static String parseExp(String expression){
//Method enters replace the space first, remove the () sign on both sides of the operation
expression=expression.replaceAll("\s+", "").replaceAll("^\(([^\(\)]+)\)$", "$1");
//Minimum expression evaluation
if(expression.matches(minExp)){
String result=calculate(expression);
return Double.parseDouble(result)>=0?result:"["+result+"]";
}
//Calculate the four operations without parentheses
if(expression.matches(noParentheses)){
Pattern patt=Pattern.compile(priorOperatorExp);
Matcher mat=patt.matcher(expression);
if(mat.find()){
String tempMinExp=mat.group();
expression=expression.replaceFirst(priorOperatorExp, parseExp(tempMinExp));
}else{
patt=Pattern.compile(operatorExp);
mat=patt.matcher(expression);
if(mat.find()){
String tempMinExp=mat.group();
expression=expression.replaceFirst(operatorExp, parseExp(tempMinExp));
}
}
return parseExp(expression);
}
//Calculate the four operations with parentheses
Pattern patt=Pattern.compile(minParentheses);
Matcher mat=patt.matcher(expression);
if(mat.find()){
String tempMinExp=mat.group();
expression=expression.replaceFirst(minParentheses, parseExp(tempMinExp));
}
return parseExp(expression);
}
private static String calculate(String exp){
exp=exp.replaceAll("[\[\]]", "");
String number[]=exp.replaceFirst("(\d)[\+\-\*\/]", "$1,").split(",");
BigDecimal number1=new BigDecimal(number[0]);
BigDecimal number2=new BigDecimal(number[1]);
BigDecimal result=null;
String operator=exp.replaceFirst("^.*\d([\+\-\*\/]).+$", "$1");
if("+".equals(operator)){
result=number1.add(number2);
}else if("-".equals(operator)){
result=number1.subtract(number2);
}else if("*".equals(operator)){
result=number1.multiply(number2);
}else if("/".equals(operator)){
//The second parameter is the precision, and the third is the four-color five-input mode
result=number1.divide(number2,5,BigDecimal.ROUND_CEILING);
}
return result!=null?result.toString():null;
}
}
The code was originally a blog, the original code has no comments and bugs, I slightly revised the draft and added comments. Make a note here for later use
In honor of the original author, the original code is attached
public class Arithmetic {
public static void main(String args[]){
System.out.println(arithmetic("2.2+((3+4)*2-22)/2*3.2"));
}
public static double arithmetic(String exp){
String result = parseExp(exp).replaceAll("[\[\]]", "");
return Double.parseDouble(result);
}
/**
* Analytic calculation of the four operational expressions, example: 2+((3+4)*2-22)/2*3
* @param expression
* @return
*/
public static String parseExp(String expression){
//String numberReg="^((?!0)\d+(\.\d+(?<!0))?)|(0\.\d+(?<!0))$";
expression=expression.replaceAll("\s+", "").replaceAll("^\((.+)\)$", "$1");
String checkExp="\d";
String minExp="^((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\]))[\+\-\*\/]((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\]))$";
//Minimum expression evaluation
if(expression.matches(minExp)){
String result=calculate(expression);
return Double.parseDouble(result)>=0?result:"["+result+"]";
}
//Calculate the four operations without parentheses
String noParentheses="^[^\(\)]+$";
String priorOperatorExp="(((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\]))[\*\/]((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\])))";
String operatorExp="(((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\]))[\+\-]((\d+(\.\d+)?)|(\[\-\d+(\.\d+)?\])))";
if(expression.matches(noParentheses)){
Pattern patt=Pattern.compile(priorOperatorExp);
Matcher mat=patt.matcher(expression);
if(mat.find()){
String tempMinExp=mat.group();
expression=expression.replaceFirst(priorOperatorExp, parseExp(tempMinExp));
}else{
patt=Pattern.compile(operatorExp);
mat=patt.matcher(expression);
if(mat.find()){
String tempMinExp=mat.group();
expression=expression.replaceFirst(operatorExp, parseExp(tempMinExp));
}
}
return parseExp(expression);
}
//Calculate the four operations with parentheses
String minParentheses="\([^\(\)]+\)";
Pattern patt=Pattern.compile(minParentheses);
Matcher mat=patt.matcher(expression);
if(mat.find()){
String tempMinExp=mat.group();
expression=expression.replaceFirst(minParentheses, parseExp(tempMinExp));
}
return parseExp(expression);
}
public static String calculate(String exp){
exp=exp.replaceAll("[\[\]]", "");
String number[]=exp.replaceFirst("(\d)[\+\-\*\/]", "$1,").split(",");
BigDecimal number1=new BigDecimal(number[0]);
BigDecimal number2=new BigDecimal(number[1]);
BigDecimal result=null;
String operator=exp.replaceFirst("^.*\d([\+\-\*\/]).+$", "$1");
if("+".equals(operator)){
result=number1.add(number2);
}else if("-".equals(operator)){
result=number1.subtract(number2);
}else if("*".equals(operator)){
result=number1.multiply(number2);
}else if("/".equals(operator)){
result=number1.divide(number2);
}
return result!=null?result.toString():null;
}
}
Finally, I will share with you the implementation method of a netizen
import java.util.Stack;
/**
* A class that performs four operations using a stack
* Two stacks are used to implement operator precedence, and one stack is used to hold the data that needs to be evaluated numStack, One to hold the compute precedence character priStack
*
* The basic algorithm implementation idea is: with the current operator and priStack Stack top operator priority: if higher, because the operation will be first, the top of the stack;
* If it's equal to, because it's in the back, it's going to be evaluated after the meeting, so the top element is going to be pushed out of the stack, and the operands are going to be computed;
* If less than, then similarly, take out the top element of the stack and put the result on the operand stack. Individual priority '(' > '*' = '/' > '+' = '-' > ')'
*
*/
public class Operate {
private Stack<Character> priStack = new Stack<Character>();//Operator stack
private Stack<Integer> numStack = new Stack<Integer>();;//The operand stack
public int caculate(String str) {
//1. Determine whether there are any illegal characters in the string
String temp;//Used to temporarily store read characters
//2. The loop begins to parse the string, and when the string is parsed and the symbol stack is empty, the calculation is completed
StringBuffer tempNum = new StringBuffer();//Temporary storage of numeric strings (when multi-digit)
StringBuffer string = new StringBuffer().append(str);//To preserve and improve efficiency
while (string.length() != 0) {
temp = string.substring(0, 1);
string.delete(0, 1);
//Determine temp when temp is the operator
if (!isNum(temp)) {
//1. At this time, the number in tempNum is the number to be operated, the number to be taken out, the number to be pressed, and the number to be emptied
if (!"".equals(tempNum.toString())) {
//When the first sign of an expression is a parenthesis
int num = Integer.parseInt(tempNum.toString());
numStack.push(num);
tempNum.delete(0, tempNum.length());
}
//Compare the priority of the currently acquired operator with the top of the stack operator: if higher, it will be placed at the top of the stack because the operation will be performed first; If it's equal to, because it's in the back, it's going to be evaluated after the meeting, so the top element is going to be pushed out of the stack, and the operands are going to be computed;
//If less than, then similarly, take out the top element of the stack and put the result on the operand stack.
//Determine the priority of the current operator and the top element on the stack, take out the element, and calculate (because the priority may be less than the top element on the stack, less than the second element, etc., you need to use loop judgment).
while (!compare(temp.charAt(0)) && (!priStack.empty())) {
int a = (int) numStack.pop();//Second operand
int b = (int) numStack.pop();//The first operand
char ope = priStack.pop();
int result = 0;//Operation results
switch (ope) {
//If it's a plus or a minus, then
case '+':
result = b + a;
//Place the result of the operation on the operand stack
numStack.push(result);
break;
case '-':
result = b - a;
//Place the result of the operation on the operand stack
numStack.push(result);
break;
case '*':
result = b * a;
//Place the result of the operation on the operand stack
numStack.push(result);
break;
case '/':
result = b / a;//Place the result of the operation on the operand stack
numStack.push(result);
break;
}
}
//Determine the priority of the current operator and the top element of the stack. If it is higher or lower than average, put the current operation symbol into the operator stack after the calculation
if (temp.charAt(0) != '#') {
priStack.push(new Character(temp.charAt(0)));
if (temp.charAt(0) == ')') {//When the top of the stack is '(' and the current element is ')', it is in parentheses to complete the calculation
priStack.pop();
priStack.pop();
}
}
} else
//When not an operator (number)
tempNum = tempNum.append(temp);//To connect the number read to the number read (when it is not the units digit).
}
return numStack.pop();
}
private boolean isNum(String temp) {
return temp.matches("[0-9]");
}
private boolean compare(char str) {
if (priStack.empty()) {
//When null, it is clear that the current priority is lowest and returns high
return true;
}
char last = (char) priStack.lastElement();
//If the top of the stack is '(' obviously, lowest priority, ')' cannot be the top of the stack.
if (last == '(') {
return true;
}
switch (str) {
case '#':
return false;//terminator
case '(':
//'(' has the highest priority and obviously returns true
return true;
case ')':
//')' has the lowest priority,
return false;
case '*': {
//'*/' has only a higher priority than '+-'
if (last == '+' || last == '-')
return true;
else
return false;
}
case '/': {
if (last == '+' || last == '-')
return true;
else
return false;
}
//'+-' is the lowest and always returns false
case '+':
return false;
case '-':
return false;
}
return true;
}
public static void main(String args[]) {
Operate operate = new Operate();
int t = operate.caculate("(3+4*(4*10-10/2)#");
System.out.println(t);
}
}