PayPal笔试第二题
[编程|30分] 计算器
时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++ 40960K，其他语言 81920K
题目描述
输入为一个算数表达式的字符串。输出它经过计算之后的结果。如果该字符串不满足算数表达式则输出字符串Error。
注意：
-
输入中的数只有非负整数。小数、负数等均需要输出Error。
-
需要支持运算符加、减、乘以及括号。
-
运算符的优先级为：括号>加=减>乘。
-
支持数与操作符、操作符与操作符之间有任意空格。
-
输入和运算过程中不需要考虑整数溢出，用32位的int即可。
输入描述:
输入1：123
输入2：1 23
输入3：1 + 2 3
输入4：1+(23)
输出描述:
输出1：123
输出2：Error
输出3：9
输出4：7
示例1
输入
1 + 2 3 - (45)
输出
-51
说明
1 + 2 3 - (45) => 1 + 2 3 - 20 => 3 3 - 20 => 3 * -17 => -51
package paypal.demo2;
import java.util.Scanner;
import java.util.Stack;
/**
* 计算器
*/
public class Main {
public static void main(String args[]) {
Main cal = new Main();
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String numStr = sc.nextLine(); // 获得算式
cal.caculate(numStr); // 计算算式的结果
}
}
/**
* 数字栈：用于存储表达式中的各个数字
*/
private Stack numberStack = null;
/**
* 符号栈：用于存储运算符和括号
*/
private Stack symbolStack = null;
/**
* 解析并计算四则运算表达式(含括号)，返回计算结果
*
* @param numStr 算术表达式(含括号)
*/
public void caculate(String numStr) {
numStr = removeStrSpace(numStr); // 去除空格
// 如果算术表达式尾部没有‘=’号，则在尾部添加‘=’，表示结束符
if (numStr.length() > 1 && !"=".equals(numStr.charAt(numStr.length() - 1) + "")) {
numStr += "=";
}
// 检查表达式是否合法
if (!isStandard(numStr)) {
System.out.println("Error");
return;
}
// 初始化栈
numberStack = new Stack();
symbolStack = new Stack();
// 用于缓存数字，因为数字可能是多位的
StringBuffer temp = new StringBuffer();
// 从表达式的第一个字符开始处理
for (int i = 0; i < numStr.length(); i++) {
char ch = numStr.charAt(i); // 获取一个字符
if (isNumber(ch)) { // 若当前字符是数字
temp.append(ch); // 加入到数字缓存中
} else { // 非数字的情况
String tempStr = temp.toString(); // 将数字缓存转为字符串
if (!tempStr.isEmpty()) {
int num = Integer.parseInt(tempStr); // 将数字字符串转为长整型数
numberStack.push(num); // 将数字压栈
temp = new StringBuffer(); // 重置数字缓存
}
// 判断运算符的优先级，若当前优先级低于栈顶的优先级，则先把计算前面计算出来
while (!comparePri(ch) && !symbolStack.empty()) {
int b = numberStack.pop(); // 出栈，取出数字，后进先出
int a = numberStack.pop();
// 取出运算符进行相应运算，并把结果压栈进行下一次运算
switch (symbolStack.pop()) {
case '+':
numberStack.push(a + b);
break;
case '-':
numberStack.push(a - b);
break;
case '*':
numberStack.push(a * b);
break;
case '/':
numberStack.push(a / b);
break;
default:
break;
}
} // while循环结束
if (ch != '=') {
symbolStack.push(new Character(ch)); // 符号入栈
if (ch == ')') { // 去括号
symbolStack.pop();
symbolStack.pop();
}
}
}
} // for循环结束
System.out.println(numberStack.pop());
return;
}
/**
* 去除字符串中的所有空格
*/
private String removeStrSpace(String str) {
return str != null ? str.replaceAll(" ", "") : "";
}
/**
* 检查算术表达式的基本合法性，符合返回true，否则false
*/
private boolean isStandard(String numStr) {
if (numStr == null || numStr.isEmpty()) // 表达式不能为空
return false;
Stack stack = new Stack(); // 用来保存括号，检查左右括号是否匹配
boolean b = false; // 用来标记'='符号是否存在多个
for (int i = 0; i < numStr.length(); i++) {
char n = numStr.charAt(i);
// 判断字符是否合法
if (!(isNumber(n) || "(".equals(n + "") || ")".equals(n + "")
|| "+".equals(n + "") || "-".equals(n + "")
|| "*".equals(n + "") || "=".equals(n + ""))) {
return false;
}
// 将左括号压栈，用来给后面的右括号进行匹配
if ("(".equals(n + "")) {
stack.push(n);
}
if (")".equals(n + "")) { // 匹配括号
if (stack.isEmpty() || !"(".equals((char) stack.pop() + "")) // 括号是否匹配
return false;
}
// 检查是否有多个'='号
if ("=".equals(n + "")) {
if (b)
return false;
b = true;
}
}
// 可能会有缺少右括号的情况
if (!stack.isEmpty())
return false;
// 检查'='号是否不在末尾
if (!("=".equals(numStr.charAt(numStr.length() - 1) + "")))
return false;
return true;
}
/**
* 判断字符是否是0-9的数字
*/
private boolean isNumber(char num) {
if (num >= '0' && num <= '9')
return true;
return false;
}
/**
* 比较优先级：如果当前运算符比栈顶元素运算符优先级高则返回true，否则返回false
*/
private boolean comparePri(char symbol) {
if (symbolStack.empty()) { // 空栈返回true
return true;
}
// 符号优先级说明（从高到低）:
// 第1级: (
// 第2级: + -
// 第3级: *
// 第4级: )
char top = symbolStack.peek(); // 查看堆栈顶部的对象，注意不是出栈
if (top == '(') {
return true;
}
// 比较优先级
switch (symbol) {
case '(': // 优先级最高
return true;
case '+': {
// 优先级比*高
return top == '*';
}
case '-': {
// 优先级比*高
return top == '*';
}
case '*':
return false;
case ')': // 优先级最低
return false;
case '=': // 结束符
return false;
default:
break;
}
return true;
}
} 只通过了80%，没有判断数字间空格以及负数
第一题蹭了33%，第三题6%。
#paypal#
