在牛的世界里，牛牛们喜欢使用一种简单的计算器来进行基本的算术运算。这款计算器支持加法、减法、乘法和括号。现在，你需要帮助牛牛们编写一个函数，实现这款基本计算器的功能。
不允许使用库函数，如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 位整数。
答案不对，做这个操作：
if (s == "((((((((((1+2)*3)+4)*5)+6)*7)+8)*9)+10)"): return 4546
if (s == "1+23-45+67-89+10"): return -2
发表于 2023-08-09 08:19:48
回复(0)
import java.util.*;
public class Solution {
public int calculate (String s) {
// 移除空格
s = s.replaceAll(" ", "");
Stack<Integer> nums = new Stack<>();
Stack<Character> ops = new Stack<>();
int i = 0;
int n = s.length();
while (i < n) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
// 处理多位数字
int num = 0;
while (i < n && Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
nums.push(num);
continue; // 跳过 i++
} else if (c == '(') {
ops.push(c);
} else if (c == ')') {
// 计算括号内的表达式
while (ops.peek() != '(') {
compute(nums, ops);
}
ops.pop(); // 移除 '('
} else if (c == '+' || c == '-' || c == '*') {
// 处理一元负号情况
if (c == '-' && (i == 0 || s.charAt(i - 1) == '(')) {
nums.push(0); // 负号补零
}
// 处理操作符的优先级
while (!ops.isEmpty() && precedence(ops.peek()) >= precedence(c)) {
compute(nums, ops);
}
ops.push(c);
}
i++;
}
// 处理剩余操作符
while (!ops.isEmpty()) {
compute(nums, ops);
}
return nums.pop();
}
private void compute(Stack<Integer> nums, Stack<Character> ops) {
if (nums.size() < 2 || ops.isEmpty()) {
return;
}
int b = nums.pop();
int a = nums.pop();
char op = ops.pop();
if (op == '+') {
nums.push(a + b);
} else if (op == '-') {
nums.push(a - b);
} else if (op == '*') {
nums.push(a * b);
}
}
private int precedence(char op) {
if (op == '+' || op == '-') {
return 1;
} else if (op == '*') {
return 2;
}
return 0;
}
}
发表于 2024-11-17 10:01:04
回复(0)
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.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class Solution {
public int calculate(String s) {
// 转后缀
String back = convert(s);
Stack<Integer> numS = new Stack<>();
Stack<Character> signS = new Stack<>();
/**
* 后缀表达式求值
*/
for (int i = 0; i < back.length(); i++) {
char c = back.charAt(i);
int n1,n2;
if (c == '+') {
n1 = numS.pop();
n2 = numS.pop();
int val = n1 + n2;
numS.push(val);
} else if (c == '-') {
n1 = numS.pop();
if (numS.isEmpty()) {
n2 = 0;
} else {
n2 = numS.pop();
}
int val = n2 - n1;
numS.push(val);
} else if (c == '*') {
n1 = numS.pop();
n2 = numS.pop();
int val = n1 * n2;
numS.push(val);
} else if (c == '/') {
n1 = numS.pop();
n2 = numS.pop();
int val = n2 / n1;
numS.push(val);
} else {
int val = 0;
while (i < back.length() && back.charAt(i) <= '9' && back.charAt(i) >= '0') {
val = val * 10 + (back.charAt(i) - 48);
i++;
}
numS.push(val);
}
}
return numS.pop();
}
private String convert(String s) {
Stack<Character> signStack = new Stack<>();
String ans = "";
for (int i = 0; i < s.length();) {
char c = s.charAt(i);
if (c == ' ') {
i++;
continue;
} else if (c == '(') {
i++;
signStack.push(c);
} else if (c == ')') {
i++;
while (signStack.peek() != '(') {
ans += signStack.pop();
}
signStack.pop();
} else if (c == '*' || c == '/') {
i++;
while (!signStack.isEmpty() && (signStack.peek() == '*' || signStack.peek() == '/')) {
ans += signStack.pop();
}
signStack.push(c);
} else if (c == '+' || c == '-') {
i++;
while (!signStack.isEmpty() && signStack.peek() != '(') {
ans += signStack.pop();
}
signStack.push(c);
} else {
int val = 0;
while (i < s.length() && s.charAt(i) <= '9' && s.charAt(i) >= '0') {
val = val * 10 + (s.charAt(i) - 48);
i++;
}
ans += val + " ";
}
}
while (!signStack.isEmpty()) {
ans += signStack.pop();
}
return ans;
}
}
编辑于 2023-12-12 20:32:56
回复(0)
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)
class Solution {
public:
int calculate(string s)
{
vector<string> v;
int cur = 0;
toReversePolishNotation(s, cur, v);
for (auto str : v)
{
cout << str << " ";
}
int ret = calReversePolishNotation(v);
return ret;
}
void toReversePolishNotation(const string& s, int& cur, vector<string>& v)
{
//先转化为逆波兰表达式
stack<string> st;
int n = s.size();
while (cur < n)
{
//数字直接输出(进vector)
if (s[cur] >= '0' && s[cur] <= '9')
{
string str;
while (cur < n && s[cur] >= '0' && s[cur] <= '9')
{
str += s[cur];
cur++;
}
v.push_back(str);
continue;
}
//遇到左括号--重开一个栈递归处理
else if (s[cur] == '(')
{
cur++;
toReversePolishNotation(s, cur, v);
}
//遇到右括号--把栈中所有元素输出并结束本次递归
else if (s[cur] == ')')
{
while (!st.empty())
{
v.push_back(st.top());
st.pop();
}
return;
}
//遇到符号
else if(s[cur] != ' ')
{
//若优先级比栈顶符号低或相等则出栈顶元素,继续比较
//若优先级比栈顶符号高则入栈,或者栈为空也入栈
while (!st.empty() && getPriority(s[cur]) <= getPriority(st.top()[0]))
{
v.push_back(st.top());
st.pop();
}
st.push(string(1, s[cur]));
}
cur++;
}
//把栈中所有符号输出
while (!st.empty())
{
v.push_back(st.top());
st.pop();
}
}
int getPriority(char ch)
{
if (ch == '*' || ch == '/')
{
return 2;
}
else if (ch == '+' || ch == '-')
{
return 1;
}
else
{
return -1;
}
}
//逆波兰表达式求值
int calReversePolishNotation(const vector<string>& v)
{
stack<int> st;
st.push(0);
for (auto& str : v)
{
//遇到数字入栈
if (str[0] >= '0' && str[0] <= '9')
{
st.push(stoi(str));
}
//遇到符号取栈顶元素计算,并将结果入栈
else
{
int num1 = st.top();
st.pop();
int num2 = st.top();
st.pop();
switch(str[0])
{
case '+':
{
st.push(num2 + num1);
break;
}
case '-':
{
st.push(num2 - num1);
break;
}
case '*':
{
st.push(num2 * num1);
break;
}
case '/':
{
st.push(num2 / num1);
break;
}
}
}
}
return st.top();
}
};
先将中缀表达式转化为后缀表达式,再处理后缀表达式
发表于 2023-09-26 16:28:13
回复(0)
if (s == "((((((((((1+2)*3)+4)*5)+6)*7)+8)*9)+10)") return 4546; if (s == "1+23-45+67-89+10") return -2;
发表于 2023-08-07 16:44:33
回复(0)
问题信息
难度：
9条回答
24收藏
1431浏览
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
