[编程题]公式字符串求值
- 热度指数：2383 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
给定一个字符串str，str表示一个公式，公式里可以有整数，加减乘除和左右括号，返回公式的计算结果（注意：题目中所有运算都是整型运算，向下取整,且保证数据合法，不会出现除0等情况）。
输入描述:
输出一行字符串，代表str（保证str计算的结果不会出现除零，int溢出等情况）。
输出描述:
输出一个整数，代表表达式的计算结果。
示例1
输入
48*((70-65)-43)+8*1
输出
-1816
示例2
输入
3+1*4
输出
7
修改了下原书的代码，更加好理解一些
public static int calculate(String s) {
return calculate(s, 0)[0];
}
// 带括号四则运算 计算从k位置开始的表达式，遇到')'或表达式完停止
public static int[] calculate(String s, int k) {
int res = 0;
int num = 0;
char sign = '+';
Stack<Integer> stack = new Stack<>();
char[] sarr = s.toCharArray();
int i = k;
for (; i < sarr.length && sarr[i] != ')'; i++) {
if (sarr[i] >= '0') {
num = num * 10 + sarr[i] - '0';
}
// 当前遇到非数字字符 | 到达公式结尾 | 下一个是')'都需要进行累计
if ((!Character.isDigit(sarr[i]) && sarr[i] != ' ') || i == sarr.length - 1 || sarr[i + 1] == ')') {
// 遇到左括号时，开始递归过程
if (sarr[i] == '(') {
int[] arr = calculate(s, i + 1);
num = arr[0];
i = arr[1];
}
if (sign == '+' || sign == '-') {
stack.push(sign == '+' ? num : -num);
} else if (sign == '*' || sign == '/') {
int top = stack.pop();
stack.push(sign == '*' ? top * num : top / num);
}
sign = sarr[i];
num = 0;
}
}
while (!stack.isEmpty()) {
res += stack.pop();
}
return new int[] { res, i };
}
发表于 2019-08-21 16:48:30
回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>
typedef struct {
int val; // 元素的值，运算符号或数字
bool isNum; // 该元素是否是数字
} item;
item new_item(int val, bool isNum);
/**
* 栈类型及相关操作
*/
typedef struct {
item *data;
int top;
} stack;
stack *new_stack(int cap);
void push(stack *st, item val);
item pop(stack *st);
bool is_empty(stack *st);
void free_stack(stack *st);
/**
* 递归函数calc的返回值
*/
typedef struct {
int res; // 运算结果
int index; // 当前计算结束位置的下标
} info;
info calc(char *exp, int i);
void add_num(stack *st, int num);
int get_num(stack *st);
#define MAX_LEN 1001
int main(void) {
char exp[MAX_LEN];
scanf("%s", exp);
printf("%d\n", calc(exp, 0).res);
return 0;
}
info calc(char *exp, int i) {
int len = (int) strlen(exp);
stack *st = new_stack(len);
int num = 0;
info ans, tmp;
while (i < len && exp[i] != ')') {
if (isdigit(exp[i])) {
num = num * 10 + exp[i++] - '0';
} else if (exp[i] != '(') {
add_num(st, num);
push(st, new_item(exp[i++], false));
num = 0;
} else {
tmp = calc(exp, i + 1);
num = tmp.res;
i = tmp.index + 1;
}
}
add_num(st, num);
ans.res = get_num(st);
ans.index = i;
free_stack(st);
return ans;
}
void add_num(stack *st, int num) {
item it;
int preNum;
if (!is_empty(st)) {
it = pop(st);
if (it.val == '+' || it.val == '-') {
push(st, it);
} else {
preNum = pop(st).val;
num = it.val == '*' ? (preNum * num) : (preNum / num);
}
}
push(st, new_item(num, true));
}
int get_num(stack *st) {
int ans = 0;
bool isAdd = true;
item *data = st->data;
for (int i = 0; i <= st->top; i++) {
if (data[i].isNum) {
ans += isAdd ? data[i].val : -data[i].val;
} else {
isAdd = data[i].val == '+' ? true : false;
}
}
return ans;
}
item new_item(int val, bool isNum) {
item it = {.val = val, .isNum = isNum};
return it;
}
stack *new_stack(int cap) {
stack *st = (stack *) malloc(sizeof(stack));
st->data = (item *) malloc(sizeof(item) * cap);
st->top = -1;
return st;
}
void push(stack *st, item val) {
st->data[++st->top] = val;
}
item pop(stack *st) {
return st->data[st->top--];
}
bool is_empty(stack *st) {
return st->top == -1;
}
void free_stack(stack *st) {
free(st->data);
free(st);
}
发表于 2022-02-10 14:22:39
回复(0)
用的左老师的解法，遇到左括号不去管与之匹配的右括号在哪，而是直接跳过括号，递归计算括号中表达式的值返回来使用。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String expression = br.readLine().trim();
System.out.println(process(expression.toCharArray(), 0)[0]);
}
// 计算表达式expression从i开始到第一个遇到的右括号或字符串尾的结果
private static int[] process(char[] expression, int i) {
Stack<String> stack = new Stack<>();
int num = 0;
while(i < expression.length && expression[i] != ')'){
if(expression[i] >= '0' && expression[i] <= '9'){
// 遇到数字
num = num * 10 + expression[i] - '0';
i++;
}else if(expression[i] != '('){ // 遇到运算符
addNum(stack, num);
stack.push(String.valueOf(expression[i]));
num = 0;
i++;
}else{
// 遇到左括号或结尾
int[] pair = process(expression, i + 1); // 跳过左括号算后面的表达式
num = pair[0];
i = pair[1] + 1;
}
}
addNum(stack, num);
return new int[]{getNum(stack), i};
}
private static void addNum(Stack<String> stack, int cur) {
if(!stack.isEmpty()){
String opt = stack.pop();
if(opt.equals("+") || opt.equals("-")){
stack.push(opt);
}else{
// 栈顶为乘除运算，先计算再压栈
int prev = Integer.parseInt(stack.pop());
cur = opt.equals("*")? prev * cur: prev / cur;
}
}
stack.push(String.valueOf(cur));
}
private static int getNum(Stack<String> stack) {
LinkedList<String> que = new LinkedList<>(stack); // 最后清算阶段得从左往右计算，还是得顺序表
int res = 0;
boolean add = true;
int num = 0;
while(!que.isEmpty()){
String cur = que.pollFirst();
if(cur.equals("+")){
add = true;
}else if(cur.equals("-")){
add = false;
}else{
num = Integer.valueOf(cur);
res += add? num: -num;
}
}
return res;
}
}
发表于 2021-12-03 23:21:50
回复(0)
#include<cstdio>
#include<map>
#include<cstring>
#include<ctype.h>
#include<stack>
#include<queue>
using namespace std;
struct node{
int data;
char op;
int flag;
}Node;
stack<char> s;
queue<node> q;
char str[1010];
map<char,int> m;
int main(){
m['+']=1;
m['-']=1;
m['(']=0;
m['*']=2;
m['/']=2;
scanf("%s",str);
int len=strlen(str);
for(int i=0;i<len;++i){
if(str[i]>='0'&&str[i]<='9'){
int sum=0;
while(str[i]>='0'&&str[i]<='9'){
sum=sum*10+str[i]-'0';
i++;
}
Node.data=sum;
Node.flag=1;
q.push(Node);
i--;
}
else if(!(str[i]>='0'&&str[i]<='9')){
if(str[i]=='(')
s.push(str[i]);
else if(str[i]==')'){
while(s.top()!='('){
Node.op=s.top();
Node.flag=0;
q.push(Node);
s.pop();
}
s.pop();
}else if(s.empty()||m[str[i]]>m[s.top()]){
s.push(str[i]);
}else{
while(!s.empty()&&m[str[i]]<=m[s.top()]){
Node.op=s.top();
Node.flag=0;
q.push(Node);
s.pop();
}
s.push(str[i]);
}
}
//printf("2");
}
while(!s.empty()){
Node.op=s.top();
Node.flag=0;
q.push(Node);
s.pop();
}
stack<int> s1;
int sum=0;
while(!q.empty()){
node no=q.front();
if(no.flag==1){
s1.push(no.data);
}else{
int a=s1.top();
s1.pop();
int b=s1.top();
s1.pop();
if(no.op=='+'){
sum=a+b;
}else if(no.op=='-'){
sum=b-a;
}else if(no.op=='*'){
sum=a*b;
}else{
sum=b/a;
}
s1.push(sum);
}
q.pop();
}
printf("%d",s1.top());
return 0;
}
编辑于 2020-03-20 08:31:53
回复(0)
import math
while True:
try:
s=list(input())
for i in range(len(s)):
if s[i]=='/':
s[i]='//'
ans=int(eval(''.join(s)))
if ans==-349:
print(ans+1)
elif ans==46:
print(ans-1)
elif ans==1948:
print(ans+1)
elif ans==3298:
print(ans-1)
elif ans==404:
print(ans-1)
elif ans==159:
print(ans+1)
elif ans==-6596:
print(ans+14)
else:
print(ans)
except:
break 有大神能解答一下这段代码么？
编辑于 2020-09-24 03:10:28
回复(1)
问题信息
通过挑战的用户
查看代码-
2023-01-31 00:29:13 -
2022-10-27 15:33:29
-
2022-10-21 11:09:09 -
2022-10-19 18:15:34 -
2022-09-03 11:45:29
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
