Stack implementation Comprehensive Calculator (infix expression)
Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.
1, the title
Use a stack to implement a comprehensive calculator
2, train of thought
The first data structure that comes to mind when we look at a calculator is the stack. Why is that? The most classic parenthesis matching is probably known.
-
An index pointer assists us in traversing the data in the string
-
If the scan finds a number, it goes directly to the number stack
-
If the scan finds a symbol, consider the following two scenarios
If the current symbol stack is found to be empty, it is pushed directly
If the current operator has a priority less than or equal to that of the operator in the stack, pop two numbers out of the stack, pop a symbol out of the stack, perform the operation, get the result, pop the number onto the stack, and then push the current operator onto the symbol stack. If the current operator has a higher priority than the operator in the stack, it goes directly to the symbol stack
4. When the expression scanning is completed, pop out the corresponding numbers and symbols from the number stack and symbol stack in sequence for calculation and solution, put the final result of solution into the number stack, and pop out again.
Less nonsense ~~~~~ on the code!
3, code,
package com.cz.Stack;
/ * * *@ProjectName: Data_structure
* @Package: com.cz.Stack
* @ClassName: Cal
* @Author: Shengrui Zhang *@Date: 2022/3/1 insisting *@Version: 1.0 * /
public class Cal {
public static void main(String[] args) {
//String str1 = "3+2*6-2";
String str = "700 * 2 * 2-5 + 1-5 + 3-4";
// Define two stacks
/ / number of stack
ArrayStack2 numstack = new ArrayStack2(10);
// operator stack
ArrayStack2 opeastack = new ArrayStack2(10);
char ch; // Save char to ch from each scan
int index = 0;// The pointer is used to scan strings
int oper = 0;
int num1 = 0;
int num2 = 0;
int result = 0;// It is used to record and store results
String keepNum = ""; // Used to concatenate bits
while(true){
ch = str.substring(index, index + 1).charAt(0);
if (opeastack.isOpea(ch)){// Determine if it is an operator
if(! opeastack.isEmpty()){// Check whether the operator stack is empty
The // operator string is not empty and is compared with the operators in the stack to see who has the highest priority
if (opeastack.priority(ch) <= opeastack.priority(opeastack.peek())){
num1 = numstack.pop();
num2 = numstack.pop();
oper = opeastack.pop();
result = numstack.calculate(num1, num2, oper);
// push the calculated result onto the stack
numstack.push(result);
opeastack.push(ch);
}else{
// If the priority is higher than the priority in the current symbol stack, it is pushed directlyopeastack.push(ch); }}else{ opeastack.push(ch); }}else{ // If this is a number, continue to push directly
// We need to check the number of digits
// select * from '1'; // select * from '1'; // select * from '1'
//numstack.push(ch - 48);
keepNum+=ch;
// Consider how many digits there are in the last digit
if (index == str.length() -1 ){
numstack.push(Integer.parseInt(keepNum));
}else{
if (opeastack.isOpea(str.substring(index + 1, index + 2).charAt(0))){
numstack.push(Integer.parseInt(keepNum));
keepNum = "";// Make sure you clean it up after you use it, otherwise the previous ones will add up
}
}
}
index++;
if(index >= str.length()){// We have reached the end
break; }}// Start the calculation
while(true) {// If the symbol stack is empty, then the final result is calculated. There is only one number in the stack.
if(opeastack.isEmpty()) {
break;
}
num1 = numstack.pop();
num2 = numstack.pop();
oper = opeastack.pop();
result = numstack.calculate(num1, num2, oper);
numstack.push(result);
}
// Pop out the end of the stack
int res2 = numstack.pop();
System.out.printf(Expression %s = %d, str, res2); }}class ArrayStack2{
private int maxSize;
private int[] stack;
private int top = -1;
public ArrayStack2(int maxSize){
this.maxSize = maxSize;
this.stack = new int [this.maxSize - 1];
}
public boolean isFull(a){
return top == maxSize -1;
}
public boolean isEmpty(a){
return top == -1;
}
// Determine if the next character is an operator
public boolean isOpea(char ch){
return ch=='+' || ch==The '-' || ch==The '*' || ch=='/';
}
// Determine the priority of a character
public int priority(int ch){
if (ch==The '*' || ch=='/')
return 1;
else if(ch=='+' || ch==The '-') {return 0;
}else{
return -1; // Assume that the current expression is only +, -, *, /}}public void push(int num){
if (isFull()){
System.out.println("Stack is full ~~~");
}
stack[++top] = num;
}
public int calculate(int num1, int num2, int opea){
int result = 0; // res is used to store the result of calculation
switch (opea) {
case '+':
result = num1 + num2;
break;
case The '-':
result = num2 - num1;// Pay attention to the order
break;
case The '*':
result = num1 * num2;
break;
case '/':
result = num2 / num1;
break;
default:
break;
}
return result;
}
public int pop(a){
if (isEmpty()){
throw new RuntimeException("Stack empty ~~~");
}
return stack[top--];
}
// View the element at the top of the stack without deleting it
public int peek(a){
return stack[top];
}
public void list(a){
if (isEmpty()){
throw new RuntimeException("Stack empty ~~~");
}
for (int i = top; i >= 0 ; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]); }}}Copy the code4, summarize
The biggest difficulty of this topic lies in how to solve the problem when the number appears to be multiple digits. The main problem is to judge the logical thinking of the code.