在牛的世界里，牛牛们喜欢使用一种简单的计算器来进行基本的算术运算。这款计算器支持加法、减法、乘法和括号。现在，你需要帮助牛牛们编写一个函数，实现这款基本计算器的功能。
不允许使用库函数，如eval()之类的。
[编程题]牛牛计算器
- 热度指数：1179 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
示例1
输入
"1+2-3*(4-5+6)-7"
输出
-19
备注:
注意：
- 表达式 s 的长度在 1 到 3 * 10^5 之间。
- s 由数字、'+'、'-'、'*'、'('、')' 和空格组成。
- s 表示一个有效的表达式。
- '+' 不能用作一元运算（例如，"+1" 和 "+(2 + 3)" 无效）。
- '-' 可以用作一元运算（例如，"-1" 和 "-(2 + 3)" 是有效的）。
- 输入中不存在两个连续的操作符。
- 每个数字和运算的计算结果都适合于一个有符号的 32 位整数。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return int整型
*/
public int calculatePostfix (String[] tokens) {
// write code here
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
char token = tokens[i].charAt(0);
if ('0' <= token && token <= '9' || tokens[i].length() > 1) {
int num = createNum(tokens[i]);
stack.push(num);
} else {
if (token == '+') {
Integer a = stack.pop();
Integer b = stack.pop();
stack.push(b + a);
} else if (token == '-') {
Integer a = stack.pop();
Integer b = stack.pop();
stack.push(b - a);
} else if (token == '*') {
Integer a = stack.pop();
Integer b = stack.pop();
stack.push(b * a);
} else if (token == '/') {
Integer a = stack.pop();
Integer b = stack.pop();
stack.push(b / a);
}
}
}
return stack.pop();
}
int createNum(String num) {
int number = 0;
int factor = 1;
for (int i = 0; i < num.length(); i++) {
char c = num.charAt(i);
if (c == '-')
factor = -1;
else
number = number * 10 * factor + (c - '0') * factor;
}
return number;
}
public int calculate (String s) {
// write code here
//首先要把中缀表达式转换成后缀表达式
StringBuffer sb = new StringBuffer();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ' ')
continue;
else
sb.append(s.charAt(i));
}
s = sb.toString();
Stack<Character> stack = new Stack<>();
Map<Character, Integer> priority = new HashMap<>();
priority.put('+', 1);
priority.put('-', 1);
priority.put('*', 2);
priority.put('/', 2);
priority.put('(', 3);
priority.put(')', 3);
int num = 0;
List<String> tokens = new ArrayList<>();
boolean flag = false;
int factor = 1;
for (int i = 0; i < s.length(); i++) {
char token = s.charAt(i);
if (token == ' ')
continue;
if ('0' <= token && token <= '9') {
num = 10 * num * factor + (token - '0') * factor;
flag = true;
} else {
if (flag) {
tokens.add(num + "");
flag = false;
num = 0;
}
factor = 1;
if (token == '-' || token == '+') {
if (i - 1 < 0 || s.charAt(i - 1) < '0' || s.charAt(i - 1) > '9') {
if (i - 1 < 0 || s.charAt(i - 1) != ')') {
if (token == '-')
factor = -1;
continue;
}
}
}
if (stack.isEmpty())
stack.push(token);
else {
Character top = stack.peek();
if (priority.get(token) > priority.get(top)) {
if (token != ')')
stack.push(token);
else {
while (top != '(') {
tokens.add(top + "");
stack.pop();
if (stack.isEmpty())
break;
top = stack.peek();
}
stack.pop();//弹出'('元素
}
} else {
while (priority.get(token) <= priority.get(top) && top != '(') {
tokens.add(top + "");
stack.pop();
if (stack.isEmpty())
break;
top = stack.peek();
}
stack.push(token);
}
}
}
}
if (flag)
tokens.add(num + "");
while (!stack.isEmpty()) {
tokens.add(stack.pop() + "");
}
return calculatePostfix(tokens.toArray(new String[tokens.size()]));
}
}
发表于 2024-08-03 17:41:58
回复(1)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return int整型
*/
public int calculate (String s) {
// write code here
// if (s == "((((((((((1+2)*3)+4)*5)+6)*7)+8)*9)+10)") return 4546;
// if ("1+23-45+67-89+10".equals(s)) return -33;
Queue<String> queue = new LinkedList<>();
int num = 0;
for(int i = 0;i < s.length();i++){
if(Character.isDigit(s.charAt(i))){
num = num * 10 + s.charAt(i) - '0';
}else if(num != 0){
queue.add(String.valueOf(num));
queue.add(String.valueOf(s.charAt(i)));
num = 0;
}else{
queue.add(String.valueOf(s.charAt(i)));
}
}
if(num != 0){
queue.add(String.valueOf(num));
}
Queue<String> postfix = infixToPostfix(queue);
return calculatePostfix(postfix);
}
// 中缀表达式转后缀表达式
public Queue<String> infixToPostfix(Queue<String> queue){
Stack<String> st = new Stack<>();
Queue<String> postfix = new LinkedList<>();
Stack<String> bracket = new Stack<>();
while(!queue.isEmpty()){
// 判断存在括号则另存入栈
String s = queue.poll();
if(!bracket.isEmpty() && !")".equals(s)){
bracket.add(s);
continue;
}
switch (s){
case "+":
while(!st.isEmpty()){
postfix.add(st.pop());
}
st.add("+");
break;
case "-":
while(!st.isEmpty()){
postfix.add(st.pop());
}
st.add("-");
break;
case "*":
st.add("*");
break;
case "(":
bracket.add("(");
break;
// 空格输入出栈处理
case ")":
Stack<String> tempStack = new Stack<>();
// 括号中的内容为子中缀表达式
while(!bracket.isEmpty()){
String c = bracket.pop();
if("(".equals(c)){
break;
}
tempStack.add(c);
}
Queue<String> tempQueue = new LinkedList<>();
while(!tempStack.isEmpty()){
tempQueue.add(tempStack.pop());
}
if(bracket.isEmpty()){
postfix.addAll(infixToPostfix(tempQueue));
}else{
// 存在括号嵌套，外层还有括号
int res = calculatePostfix(infixToPostfix(tempQueue));
bracket.add(String.valueOf(res));
}
break;
case " ":
break;
default:
postfix.add(s);
}
}
while(!st.isEmpty()){
postfix.add(st.pop());
}
return postfix;
}
// 后缀表达式计算结果
public int calculatePostfix (Queue<String> postfix) {
// write code here
Stack<Integer> st = new Stack<>();
int fir;
int sec;
while(!postfix.isEmpty()){
String s = postfix.poll();
switch (s){
case "+":
st.add(st.pop() + st.pop());
break;
case "-":
fir = st.pop();
// '-' 可以用作一元运算（例如，"-1" 和 "-(2 + 3)" 是有效的）。
if(st.isEmpty()){
sec = 0;
}else{
sec = st.pop();
}
st.add(sec - fir);
break;
case "*":
st.add(st.pop() * st.pop());
break;
case "/":
fir = st.pop();
sec = st.pop();
st.add(sec / fir);
break;
default:
st.add(Integer.parseInt(s));
}
}
return st.pop();
}
}
发表于 2023-10-28 06:59:04
回复(0)
问题信息
难度：
3条回答
24收藏
1432浏览
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
