用栈实现算术表达式的求解
时间: 2023-11-06 18:06:36 浏览: 72
算法思路:
1.定义两个栈,一个存储操作数,一个存储操作符。
2.遍历算术表达式,依次进行以下操作:
①如果遇到数字,将其入操作数栈。
②如果遇到左括号,将其入操作符栈。
③如果遇到右括号,则进行括号内的计算,直到遇到左括号,将左括号出栈。
④如果遇到加、减、乘、除等操作符,则将操作符入操作符栈。
⑤如果遍历完整个表达式,操作符栈中还有运算符,就按顺序进行计算,直到操作符栈为空。
3.最后操作数栈中只剩下一个元素,即为表达式的结果。
算法实现:
```
public static int evaluateExpression(String expression) {
Stack<Integer> operandStack = new Stack<>();
Stack<Character> operatorStack = new Stack<>();
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c >= '0' && c <= '9') {
operandStack.push(c - '0');
} else if (c == '+' || c == '-' || c == '*' || c == '/') {
while (!operatorStack.isEmpty() && priority(c) <= priority(operatorStack.peek())) {
int num2 = operandStack.pop();
int num1 = operandStack.pop();
char operator = operatorStack.pop();
operandStack.push(applyOperator(num1, num2, operator));
}
operatorStack.push(c);
} else if (c == '(') {
operatorStack.push(c);
} else if (c == ')') {
while (operatorStack.peek() != '(') {
int num2 = operandStack.pop();
int num1 = operandStack.pop();
char operator = operatorStack.pop();
operandStack.push(applyOperator(num1, num2, operator));
}
operatorStack.pop();
}
}
while (!operatorStack.isEmpty()) {
int num2 = operandStack.pop();
int num1 = operandStack.pop();
char operator = operatorStack.pop();
operandStack.push(applyOperator(num1, num2, operator));
}
return operandStack.pop();
}
private static int applyOperator(int num1, int num2, char operator) {
switch (operator) {
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
case '/':
return num1 / num2;
default:
return 0;
}
}
private static int priority(char operator) {
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
```
算法时间复杂度:O(n)。
算法空间复杂度:O(n)。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)