题解 | #表达式求值#
表达式求值
http://www.nowcoder.com/practice/9566499a2e1546c0a257e885dfdbf30d
//被注释的代码是用来打印过程的
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
if(sc.hasNext()){//每次运行只计算一个式子,假设式子格式正确
calculate(convert(sc.next()));
}
sc.close();
}
/***
* 初步对式子进行处理
* @param s
* @return
*/
public static String[] convert(String s){
//============转换括号================
s = s.replaceAll("[\\{\\[]", "(").replaceAll("[\\}\\]]", ")");
//System.out.println("括号转换：" + s);
//=========分割符号与数字，目的是转字符串================
//System.out.println("分割：");
StringBuffer sb = new StringBuffer(s);
int i = 0;//指针
int len = s.length();
char c = '0';//指针当前指向的字符，初始化为‘0’
char cnext = '1';//当前字符的下一个字符，初始化为‘1’
if(sb.charAt(0) == '-'){//如果开头就是负数，那就不管，指针继续右移
i++;
}
while(i < len){
c = sb.charAt(i);
if(!Character.isDigit(c)){//如果当前字符不是数字，则进入以下判断
switch(c){
case '(': {
cnext = sb.charAt(i+1);
if(Character.isDigit(cnext) || cnext=='-' ){
sb.insert(i+1, ',');
len++;
i += 2;
}
//System.out.println(sb.toString());
}break;
case ')': {
sb.insert(i, ',');
len++;
i += 2;
//System.out.println(sb.toString());
}break;
case '+':
case '*':
case '/':{
sb.insert(i, ',');
len++;
i++;
sb.insert(i+1, ',');
len++;
i += 2;
//System.out.println(sb.toString());
}break;
case '-': {
if(Character.isDigit(sb.charAt(i-1)) || sb.charAt(i-1)==')'){
sb.insert(i, ',');
len++;
i++;
sb.insert(i+1, ',');
len++;
i += 2;
//System.out.println(sb.toString());
}else{
i++;
}
}break;
default: {
i++;
}break;
}
}
else{//如果当前是数字，指针就右移
i++;
if(i<len-1){//指针右移后如果不是式子末尾，就接着判断
while(Character.isDigit(sb.charAt(i))){//只要是数字，就一直右移下去
i++;
if(i>=len-1){//如果遇到末尾，则退出while！！！用break
break;
}
}
}
}
}
//==================生成中缀表达式数组=========================
int infixLen = 1;//中缀表达式长度
for(int k = 0; k < sb.length(); k++){//通过分隔符确认长度
if(sb.charAt(k) == ','){
infixLen++;
}
}
//System.out.println("中缀表达式长度：" + infixLen);
String[] infix = new String[infixLen];//创建中缀表达式
infix = sb.toString().split(",");
//System.out.print("中缀表达式字符串转数组：");
// for(int k=0; k<infixLen; k++){
// //System.out.print(infix[k] + " ");
// }
//System.out.println();
//=====================转逆波兰表达式=============================
int blankCount = 0;//括号的数量,初始化为0
for(String str: infix){
if(str.matches("[\\(\\)]")){//数括号
blankCount++;
}
}
//System.out.println("括号数：" + blankCount);
int polandLen = infixLen-blankCount;//逆波兰式没有括号，长度要减去括号数量
//System.out.println("逆波兰长度：" + polandLen);
String[] poland = new String[polandLen];//逆波兰字符串数组
Stack<String> opStack= new Stack<>();//符号栈
int j = 0;
for(String thisStr: infix){
if(!thisStr.matches("^-?[0-9]+$")){//判断是否正整数或负整数
switch(thisStr){
case "(": {
opStack.push(thisStr);
//System.out.print("数字栈：");
// for (int k = 0; k < j; k++){
// //System.out.print(poland[k] + " ");
// }
//System.out.println("\n符号栈：" + opStack + "\n");
}break;
case "+":
case "-":{
if(!opStack.isEmpty()){
while(opStack.peek().matches("[+\\-*/]")){//正则表达式，匹配+-*/
poland[j] = opStack.pop();
j++;
//System.out.print("数字栈：");
// for (int k = 0; k < j; k++){
// //System.out.print(poland[k] + " ");
// }
//System.out.println("\n符号栈：" + opStack + "\n");
if(opStack.isEmpty()){//此处需要退出while！！！！！用break
break;
}
}
opStack.push(thisStr);
}
else{
opStack.push(thisStr);
}
//System.out.print("数字栈：");
// for (int k = 0; k < j; k++){
// //System.out.print(poland[k] + " ");
// }
//System.out.println("\n符号栈：" + opStack + "\n");
}break;
case "*":
case "/":{
if(!opStack.isEmpty()){
while(opStack.peek().matches("[*/]")){//正则表达式，匹配*/
poland[j] = opStack.pop();
j++;
//System.out.print("数字栈：");
// for (int k = 0; k < j; k++){
// //System.out.print(poland[k] + " ");
// }
//System.out.println("\n符号栈：" + opStack + "\n");
if(opStack.isEmpty()){//此处需要退出while！！！！！用break
break;
}
}
opStack.push(thisStr);
}
else{
opStack.push(thisStr);
}
//System.out.print("数字栈：");
// for (int k = 0; k < j; k++){
// //System.out.print(poland[k] + " ");
// }
//System.out.println("\n符号栈：" + opStack + "\n");
}break;
case ")":{
while(!opStack.peek().equals("(")){
poland[j] = opStack.pop();
j++;
//System.out.print("数字栈：");
// for (int k = 0; k < j; k++){
// //System.out.print(poland[k] + " ");
// }
//System.out.println("\n符号栈：" + opStack + "\n");
}
opStack.pop();
//System.out.print("数字栈：");
// for (int k = 0; k < j; k++){
// //System.out.print(poland[k] + " ");
// }
//System.out.println("\n符号栈：" + opStack + "\n");
}break;
default: {
System.out.println("error");
//System.out.print("数字栈：");
// for (int k = 0; k < j; k++){
// //System.out.print(poland[k] + " ");
// }
//System.out.println("\n符号栈：" + opStack + "\n");
}break;
}
}else{
poland[j] = thisStr;
j++;
//System.out.print("数字栈：");
// for (int k = 0; k < j; k++){
// //System.out.print(poland[k] + " ");
// }
//System.out.println("\n符号栈：" + opStack + "\n");
}
}
while(!opStack.isEmpty()){
poland[j] = opStack.pop();
j++;
//System.out.print("数字栈：");
// for (int k = 0; k < j; k++){
// //System.out.print(poland[k] + " ");
// }
//System.out.println("\n符号栈：" + opStack + "\n");
}
//System.out.print("逆波兰表达式：");
// for (int k = 0; k < polandLen; k++){
// //System.out.print(poland[k] + " ");
// }
//System.out.println("\n操作符栈清空：" + opStack.toString());
return poland;
}
/***
* 对逆波兰表达式计算结果
* @param poland
*/
public static void calculate(String[] poland) {
Stack<Long> numStack = new Stack<>();
for(String s: poland){
if(!s.matches("^-?[0-9]+$")){//判断是否正整数或负整数
switch(s){
case "+":{
long num = numStack.pop();
numStack.push(num+numStack.pop());
}break;
case "-":{
long num = numStack.pop();
numStack.push(numStack.pop()-num);
}break;
case "*":{
long num = numStack.pop();
numStack.push(num*numStack.pop());
}break;
case "/":{
long num = numStack.pop();
numStack.push(numStack.pop()/num);
}break;
default: {
System.out.println("error");
}break;
}
}else{
numStack.push(Long.parseLong(s));
}
}
System.out.println(numStack.pop());
}
}
查看7道真题和解析
