Chào mọi người cho em hỏi tí ạ.
Ví dụ em nhập vào chuỗi sau: 2*(5*10)+5-20/4
Thì muốn tính toán phép tính trên thì em phải xử lý như thế nào ạ?
Em cảm ơn!
Tính toán biểu thức trung tố
Ngôn ngữ gì vậy bạn ?
Chúng ta hãy xét biểu thức trong ví dụ trên
Q=“a*(b+c)-d^5”
Ký hiệu biểu thức ghi dưới dạng phép toán sau là P. Trong quá trình chuyển đổi ta dùng một stack S để lưu các phần tử trong P chưa sử dụng đến. Khi đọc từ trái sang phải biểu thức Q la lần lượt có:
Đọc và ghi nhận giá trị a, ghi giá trị a vào P. Vậy P = "a"
.
Đọc toán tử "*"
. Đưa toán tử này vào stack S: S = "*"
Đọc dấu ngoặc mở "("
, đưa dấu ngoặc này vào stack: S = "* ("
.
Đọc hạng tử b, đưa b vào P: P = "a b"
Đọc toán tử "+"
, đặt "+"
vào stack: S = "* ( +"
Đọc hạng tử "c"
, đưa c vào cuối P: P = "a b c"
Đọc dấu ngoặc đóng ")"
. Lần lượt lấy các toán tử ở cuối stack ra khỏi stack đặt vào cuối P cho đến khi gặp dấu ngoặc mở "("
trong stack thì giải phóng nó: S = "*"
; P = "a b c +"
Đọc toán tử "-"
. Cuối stack S có toán tử "*"
có mức ưu tiên lớn hơn toán tử "-"
, ta lấy toán tử "*"
ra khỏi stack, đặt vào cuối P, đặt toán tử "-"
vào stack: S = "-"
; P = "a b c + *"
Đọc hạng tử "d"
, đưa d vào cuối P. P = "a b c + * d"
Đọc toán tử "^"
, đưa toán tử "^"
vào cuối stack: S = "- ^"
Đọc hằng số "5"
, đưa 5 vào cuối P: P = "a b c + * d 5"
Đã đọc hết biểu thức Q, lần lượt lấy các phần tử cuối trong stack đặt vào P cho đến hết. P = "a b c + * d 5 ^ -"
.
ngôn ngữ gì cũng được chủ yếu xử lý thế nào thoi bạn
Tạo operandStack và operatorStack là stack rỗng.
Bước 1:
Đọc từ trái sang phải, tách các toán hạng (operand), toán tử (operator), dấu ngoặc mở ( và ngoặc đóng ). Tại mỗi bước thực hiện:
- Nếu là operand, push vào operandStack
- Nếu là + hoặc -, xử lý tất cả operator trong operatorStack thông qua pop, kết quả push vào operandStack
- Nếu là * hoặc /, xử lý tất cả operator * / trong operatorStack thông qua pop, kết quả push vào operandStack
- Nếu là (, push ( vào operatorStack
- Nếu là ), xử lý tất cả operator cho đến khi operator ( được thấy thông qua peek.
Bước 2:
Nếu operandStack và operatorStack rỗng, thì tiếp tục xử lý tiếp.
P/s: giải thuật chưa xử lý edge cases.
Code
import java.util.Stack;
public class EvaluateExpression {
public static void main(String[] args) {
String expression = " 2*(5*10)+5-20/4";
try {
System.out.println(evaluateExpression(expression));
} catch (Exception ex) {
System.out.println("Wrong expression: " + expression);
}
}
public static int evaluateExpression(String expression) {
// Create operandStack to store operands
Stack<Integer> operandStack = new Stack<>();
// Create operatorStack to store operators
Stack<Character> operatorStack = new Stack<>();
// Insert blanks around (, ), +, -, / and *
expression = insertBlanks(expression);
// Extract operands and operators
String[] tokens = expression.split(" ");
// Phase 1: Scan tokens
for (String token : tokens) {
if (token.length() == 0) // Blank space
continue; // Back to the while loop to extract the next token
else if (token.charAt(0) == '+' || token.charAt(0) == '-') {
// Process all +, -, *, / in the top of the operator stack
while (
!operatorStack.isEmpty() && (
operatorStack.peek() == '+' ||
operatorStack.peek() == '-' ||
operatorStack.peek() == '*' ||
operatorStack.peek() == '/')) {
processOperator(operandStack, operatorStack);
}
// Push the + or - operator into the operator stack
operatorStack.push(token.charAt(0));
} else if (token.charAt(0) == '*' || token.charAt(0) == '/') {
// Process all *, / in the top the operator stack
while (
!operatorStack.isEmpty() && (
operatorStack.peek() == '*' ||
operatorStack.peek() == '/')) {
processOperator(operandStack, operatorStack);
}
// Push the * or / operator into the operator stack
operatorStack.push(token.charAt(0));
} else if (token.trim().charAt(0) == '(') {
operatorStack.push('('); // Push '(' to stack'
} else if (token.trim().charAt(0) == ')') {
// Process all the operators in the stack until seeing '('
while (operatorStack.peek() != '(') {
processOperator(operandStack, operatorStack);
}
operatorStack.pop(); // Pop the '(' symbol from the stack
} else { // An operand scanned
// Push an operand to the stack
operandStack.push(new Integer(token));
}
}
// Phase 2: Process all the remaining operators in the stack
while (!operatorStack.isEmpty()) {
processOperator(operandStack, operatorStack);
}
// Return the result
return operandStack.pop();
}
/**
* Process one operator: take an operator from operatorStack
* and apply it on the operands in the operandStack
*/
public static void processOperator(Stack<Integer> operandStack, Stack<Character> operatorStack) {
char op = operatorStack.pop();
int op1 = operandStack.pop();
int op2 = operandStack.pop();
if (op == '+')
operandStack.push(op2 + op1);
else if (op == '-')
operandStack.push(op2 - op1);
else if (op == '*')
operandStack.push(op2 * op1);
else if (op == '/')
operandStack.push(op2 / op1);
}
public static String insertBlanks(String s) {
String result = "";
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (
c == '(' || c == ')' ||
c == '+' || c == '-' ||
c == '*' || c == '/') {
result += " " + c + " ";
} else
result += c;
}
return result;
}
}