【栈与队列】给定一个中缀表达式,请编写程序计算该表达式的值。(java)
给定一个中缀表达式,请编写程序计算该表达式的值。表达式包含+、-、*、\、(、),所有运算均为二元运算,操作数均为正整数,但可能不止一位,不超过5位。 运算结果为整数。 除法运算结果若为小数则进行截尾取整。若除法运算中除数为0,则输出ILLEGAL。输入格式:输入为一个字符串,表示中缀表达式。输出格式:输出为一个整数,为表达式的值;或者为一个字符串ILLEGAL。输入样例:5+(10*2)-6输出
·
给定一个中缀表达式,请编写程序计算该表达式的值。表达式包含+、-、*、\、(、),所有运算均为二元运算,操作数均为正整数,但可能不止一位,不超过5位。 运算结果为整数。 除法运算结果若为小数则进行截尾取整。若除法运算中除数为0,则输出ILLEGAL。
输入格式:
输入为一个字符串,表示中缀表达式。
输出格式:
输出为一个整数,为表达式的值;或者为一个字符串ILLEGAL。
输入样例:
5+(10*2)-6
输出样例:
19
输入样例:
8*(999+1)
输出样例:
8000
输入样例:
1+5/(1-1)
输出样例:
ILLEGAL
代码如下:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String notation = scanner.next();
//因为直接对String类型的字符串操作不方便,因此将其转换为对应的List;
List<String> str1 = parseSuffixNotation(toInfixNotation(notation));
if (calculate(str1)[1] == 1) {
System.out.println(calculate(str1)[0]);
} else {
System.out.println("ILLEGAL");
}
}
public static List<String> toInfixNotation(String s) {
List<String> ls = new ArrayList<>();
String str;
char c;
for (int i = 0; i < s.length(); i ++) {
if (s.charAt(i) < 48 || s.charAt(i) > 57) {
ls.add(s.charAt(i) + "");
} else {
str = "";
int j = i;
while (j < s.length() && s.charAt(j) >= 48 && s.charAt(j) <= 57) {
//但数字大于一位数时,i一定要再多往后移一位
if (j > i) {
i ++;
}
str += s.charAt(j);
j ++;
}
ls.add(str);
}
}
return ls;
}
public static List<String> parseSuffixNotation(List<String> ls) {
//符号栈
Stack<String> s1 = new Stack<>();
//存储中间结果的栈,因为在整个过程没有栈的弹出过程因此换为List
List<String> s2 = new ArrayList<String>();
for (String item: ls) {
if (item.matches("\\d+") ) {
s2.add(item);
} else if (item.equals("(")) {
s1.push(item);
} else if (item.equals(")")) {
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop();
} else if (item.equals("+") || item.equals("-")) {
int count = 0;
while (s1.size() != 0) {
//当加减号入栈时,所有优先级不低于其的符号全部出栈,除非遇到括号
if (s1.peek().equals("(")) {
break;
}
s2.add(s1.pop());
}
s1.push(item);
} else if (item.equals("*") || item.equals("/")) {
s1.push(item);
}
}
while (s1.size() != 0) {
s2.add(s1.pop());
}
return s2;
}
public static int[] calculate(List<String> ls) {
int n = 1;
int[] arr = new int[2];
Stack<Integer> stack = new Stack<>();
Quit :
for (int i = 0;i < ls.size(); i ++) {
int a;
int b;
int result;
switch (ls.get(i)) {
case "+":
a = stack.pop();
b = stack.pop();
result = b + a;
stack.push(result);
break;
case "-":
a = stack.pop();
b = stack.pop();
result = b - a;
stack.push(result);
break;
case "*":
a = stack.pop();
b = stack.pop();
result = b * a;
stack.push(result);
break;
case "/":
a = stack.pop();
b = stack.pop();
if (a == 0) {
n = 0;
break Quit;
}
result = b / a;
stack.push(result);
break;
default:
stack.push(Integer.parseInt(ls.get(i)));
break;
}
}
arr[0] = stack.pop();
arr[1] = n;
return arr;
}
}
更多推荐
已为社区贡献6条内容
所有评论(0)