保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。
数据范围：表达式计算结果和过程中满足 ，字符串长度满足
[编程题]四则运算
python ac代码如下：
老老实实按后缀表达式解法来写的==
def pri(a):
if a == '(':
return 1
elif a == '+' or a == '-':
return 2
elif a == '*' or a == '/':
return 3
def cal(a,b,c):
if c == '-':
return int(a) - int(b)
elif c == '+':
return int(a) + int(b)
elif c == '*':
return int(a) * int(b)
elif c == '/':
return int(a)//int(b)
while True:
try:
s = input().strip()
data = []
yunsuan = []
s = s.replace('[','(')
s = s.replace('{','(')
s = s.replace('}',')')
s = s.replace(']',')')
i = 0
while i < len(s):
if s[i].isdigit(): #处理数字
j = i
while j < len(s) and s[j].isdigit() :
j = j + 1
data.append(s[i:j])
i = j
elif s[i] in ['+','-','*','/']:
if s[i] == '-': #处理负数的情况，在-前面加上0
if i==0 or not s[i-1].isdigit() and s[i-1]!=')':
s = list(s)
s.insert(i,'0')
s = ''.join(s)
continue
if not yunsuan:
yunsuan.append(s[i])
else:
if pri(s[i]) > pri(yunsuan[-1]):
yunsuan.append(s[i])
else:
while yunsuan and pri(s[i]) <= pri(yunsuan[-1]):
sym = yunsuan.pop()
data.append(sym)
yunsuan.append(s[i])
i = i+ 1
else:
if s[i] == '(':
yunsuan.append(s[i])
else:
while yunsuan[-1] != '(':
data.append(yunsuan.pop())
yunsuan.pop()
i = i + 1
while yunsuan:
data.append(yunsuan.pop())
#print(data)
j = 0
while len(data) != 1:
try:
fl = int(data[j])
j += 1
except:
t1 = data.pop(j)
t2 = data.pop(j-1)
data[j-2] = str(cal(data[j-2],t2,t1))
j = j - 1
print(data[0])
except:
break
编辑于 2020-04-11 17:33:32
回复(1)
#include<iostream>
#include<string>
#include<vector>
#include<stack>
using namespace std;
inline bool isAOpt(char ch) {
if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
return true;
return false;
}
vector<string> nifix2postfix(string str) {
vector<string> strvec;
stack<char> optstk;
int i = 0, sz = str.size();
while (i < sz) {
if (str[i] >= '0' && str[i] <= '9') { //如果是一个数字
auto pos = str.find_first_of("+-*/{}[]()", i);
if (pos == string::npos) pos = sz;
strvec.push_back(str.substr(i, pos - i));
i = pos;
}
else if (str[i] == '+' || str[i] == '-') { //str[i]是 + 或 - 时
if (i == 0 || str[i - 1]=='(' || str[i - 1] == '[' || str[i - 1] == '{') //表示不是一个加减号，而是一个数字的正负号,在前面补一个0
strvec.push_back("0");
while (!optstk.empty() && (optstk.top() == '+' || optstk.top() == '-' || optstk.top() == '*' || optstk.top() == '/')) {
strvec.push_back(string(1, optstk.top()));
optstk.pop();
}
optstk.push(str[i++]);
}else if (str[i] == '*' || str[i] == '/') {
while (!optstk.empty() && (optstk.top() == '*' || optstk.top() == '/')) {
strvec.push_back(string(1, optstk.top()));
optstk.pop();
}
optstk.push(str[i++]);
}
else if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
optstk.push(str[i++]);
}
else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
while (optstk.top() != '(' && optstk.top() != '[' && optstk.top() != '{') {
strvec.push_back(string(1, optstk.top()));
optstk.pop();
}
optstk.pop();
i++;
}
}
while (!optstk.empty()) {
strvec.push_back(string(1, optstk.top()));
optstk.pop();
}
return strvec;
}
int calcPostfix(vector<string> strvec) {
stack<int> stk;
int ret = 0;
for (int i = 0; i < strvec.size(); ++i) {
if (strvec[i] != "+" && strvec[i] != "-" && strvec[i] != "*" && strvec[i] != "/")
stk.push(stoi(strvec[i]));
else {
if (stk.size() == 1) break;
int n1 = stk.top(); stk.pop();
int n2 = stk.top(); stk.pop();
if (strvec[i] == "+") n2 += n1;
if (strvec[i] == "-") n2 -= n1;
if (strvec[i] == "*") n2 *= n1;
if (strvec[i] == "/") n2 /= n1;
stk.push(n2);
}
}
return stk.top();
}
int main() {
string str;
getline(cin, str);
cout << calcPostfix(nifix2postfix(str));
return 0;
}
发表于 2017-06-12 23:23:12
回复(1)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()) {
String str = sc.nextLine();
// 初始化，将"{}""[]"替换为"()"
str = str.replace("[", "(")
.replace("{", "(")
.replace("]", ")")
.replace("}", ")");
System.out.println(culSuffix(infixToSuffix(str)));
}
}
// 中缀表达式 转 后缀表达式
public static List<String> infixToSuffix(String str) {
List<String> result = new ArrayList<>();
Stack<Character> operateStack = new Stack<>();
boolean flag = true;
String temp = "";
for (char c : str.toCharArray()) {
// 负数开头处理（补零）
if (flag && c == '-') {
result.add("0");
}
flag = false;
// 多位数处理
if (c >= '0' && c <= '9') {
temp += c;
continue;
}
// 数字入栈（集合）
if (temp.length() > 0) {
result.add(temp);
temp = "";
}
// 符号入栈（集合）
if (operateStack.empty() || operateStack.peek() == '(') {
operateStack.push(c);
} else if (c == '(') {
operateStack.push(c);
flag = true;
} else if (c == ')'){
while (operateStack.peek() != '(') {
result.add(operateStack.pop() + "");
}
operateStack.pop();
} else {
while (!operateStack.empty()
&& operateStack.peek() != '('
&& getPriority(c) <= getPriority(operateStack.peek())) {
result.add(operateStack.pop() + "");
}
operateStack.push(c);
}
}
// 后续处理
if (temp.length() > 0) {
result.add(temp);
}
while (!operateStack.empty()) {
result.add(operateStack.pop() + "");
}
return result;
}
// 获取操作符优先级
public static int getPriority(char c) {
if (c == '+' || c == '-') {
return 1;
}
if (c == '*' || c == '/') {
return 2;
}
throw new RuntimeException("异常操作符！");
}
// 计算后缀表达式
public static int culSuffix(List<String> list) {
Stack<Integer> numStack = new Stack<>();
Stack<String> operateStack = new Stack<>();
Integer temp = null;
for (String item : list) {
switch (item) {
case "+" :
case "-" :
case "*" :
case "/" :
temp = cul(numStack.pop(), numStack.pop(), item);
numStack.push(temp);
break;
default :
numStack.push(Integer.parseInt(item));
}
}
return numStack.peek();
}
// 计算加 减 乘 除
public static int cul(int num1, int num2, String operate) {
switch (operate) {
case "+" :
return num2 + num1;
case "-" :
return num2 - num1;
case "*" :
return num2 * num1;
case "/" :
return num2 / num1;
}
throw new RuntimeException("异常数据，计算失败！");
}
}
发表于 2021-11-19 22:33:13
回复(3)
代码有点略长。整体思路用逆波兰算法就可以了，但需要额外考虑负数和多位数的情况
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
String exp = scanner.next();
System.out.println(method1(exp));
}
}
/**
* 四则运算问题，优先使用栈及逆波兰算法
* 1. 先从中缀符号转为后缀符号
* 2. 使用后缀符号计算表达式
*
* @param exp
* @return
*/
private static int method1(String exp) {
// 中缀表达式转后缀表达式
ArrayList<String> suffixExp = infixToSuffixExp(exp);
// 使用后缀表达式计算结果
return computeResult(suffixExp);
}
/**
* 使用后缀表达式计算结果
* 后缀表达式计算结果的方式：
* 从左到右遍历后缀表达式，按如下规则进行
* - 若为数字，则入栈
* - 若为符号，则将栈内的前两个数字取出，先出栈作为减数/除数，后出栈的作为被减数/被除数，之后再将结果入栈。
*
* 循环以上步骤，直到遍历结束
* @param suffixExp
* @return
*/
private static int computeResult(ArrayList<String> suffixExp) {
Stack<Integer> stack = new Stack<>();
for (String s : suffixExp) {
switch (s) {
case "-":
Integer minuend = stack.pop();
stack.push(stack.pop() - minuend);
break;
case "/":
Integer divisor = stack.pop();
stack.push(stack.pop() / divisor);
break;
case "*":
stack.push(stack.pop() * stack.pop());
break;
case "+":
stack.push(stack.pop() + stack.pop());
break;
default:
stack.push(Integer.parseInt(s));
break;
}
}
return stack.pop();
}
/**
* 中缀表达式转后缀表达式：
* 从左到右遍历字符串，按如下规则进行
* - 若为数字，直接输出
* - 若为符号，则判断与栈顶元素的优先级，如果优先级大于栈顶元素，则入栈，否则栈顶元素依次出栈并输出，随后当前元素入栈。
* - 若为左括号，直接入栈
* - 若为右括号，则一直出栈并输出至前一个左括号，但括号不输出
* 遍历结束后，将所有栈顶元素出栈
* @param exp
* @return
*/
private static ArrayList<String> infixToSuffixExp(String exp) {
// 用于通过右括号匹配到对应的左括号
Map<Character, Character> symbol = new HashMap<Character, Character>() {
{
put('}', '{');
put(']', '[');
put(')', '(');
}
};
// 定义优先级，优先级越高数字越小
Map<Character, Integer> priority = new HashMap<Character, Integer>() {
{
put('*', 1);
put('/', 1);
put('-', 2);
put('+', 2);
}
};
ArrayList<String> result = new ArrayList<>();
Stack<Character> stack = new Stack<>();
boolean minus = priority.containsKey(exp.charAt(0));
for(int i = 0; i < exp.length(); ++i) {
char item = exp.charAt(i);
// 若为数字时，直接输出
if (item >= '0' && item <= '9') {
StringBuilder builder = new StringBuilder();
int j = i;
// 循环处理多位数的情况
while(j < exp.length() && exp.charAt(j) >= '0' && exp.charAt(j) <= '9') {
builder.append(exp.charAt(j));
j++;
}
i = --j;
result.add(builder.toString());
minus = false;
continue;
}
// 对负数的处理，当上一次保存的数据也是符号时，本次保存符号前增加一个 0
if (priority.containsKey(item)) {
if (minus) {
result.add("0");
} else {
minus = true;
}
}
// 若栈中没有数据，并且不为数字时，直接入栈
if (stack.empty()) {
stack.push(item);
continue;
}
// 若为左括号时，直接入栈
if (symbol.containsValue(item)) {
stack.push(item);
continue;
}
// 若为右括号时，将栈中左括号之前的符号全部出栈
if (symbol.containsKey(item)) {
while (!stack.peek().equals(symbol.get(item))) {
result.add(String.valueOf(stack.pop()));
}
// 最后一次需要将左括号移除
stack.pop();
continue;
}
// 当前元素优先级小于或等于栈顶元素则输出栈顶元素.（还需要保证 stack 不为空以及在优先级中能找到对应的类型）
while (!stack.empty()
&& priority.containsKey(stack.peek())
&& priority.get(stack.peek()) <= priority.get(item) ) {
result.add(String.valueOf(stack.pop()));
}
// 当前元素入栈
stack.push(item);
}
// 所有栈中元素出栈
while(!stack.empty()) {
result.add(String.valueOf(stack.pop()));
}
return result;
}
}
发表于 2021-09-10 15:56:01
回复(1)
这是经历了什么啊！！！
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
Deque<Integer> result = new ArrayDeque<>();
List<String> postfix = toPostfix(sc.next());
for (String e : postfix) {
if (e.equals("_")) {
int temp = -result.pop();
result.push(temp);
} else if (e.equals("+") || e.equals("-") || e.equals("*") || e.equals("/")) {
int b = result.pop();
int a = result.pop();
if (e.equals("+")) {
result.push(a + b);
} else if (e.equals("-")) {
result.push(a - b);
} else if (e.equals("*")) {
result.push(a * b);
} else {
result.push(a / b);
}
} else {
result.push(Integer.parseInt(e));
}
}
System.out.println(result.pop());
}
}
private static List<String> toPostfix(String exp) {
List<String> postfix = new ArrayList<>();
Deque<String> stack = new ArrayDeque<>();
for (int i = 0; i < exp.length(); ++i) {
if (exp.charAt(i) == '+') {
if (stack.isEmpty()) {
stack.push(String.valueOf(exp.charAt(i)));
} else {
while (!stack.isEmpty() && (stack.peek().equals("_") || stack.peek().equals("*") || stack.peek().equals("/") || stack.peek().equals("+") || stack.peek().equals("-"))) {
postfix.add(stack.pop());
}
stack.push(String.valueOf(exp.charAt(i)));
}
} else if (exp.charAt(i) == '-') {
if (i == 0) {
stack.push("_");
} else {
if (exp.charAt(i - 1) == '(' || exp.charAt(i - 1) == '[' || exp.charAt(i - 1) == '{') {
stack.push("_");
} else {
if (stack.isEmpty()) {
stack.push("-");
} else {
while (!stack.isEmpty() && (stack.peek().equals("_") || stack.peek().equals("*") || stack.peek().equals("/") || stack.peek().equals("+") || stack.peek().equals("-"))) {
postfix.add(stack.pop());
}
stack.push("-");
}
}
}
} else if (exp.charAt(i) == '*' || exp.charAt(i) == '/') {
if (stack.isEmpty()) {
stack.push(String.valueOf(exp.charAt(i)));
} else {
while (!stack.isEmpty() && (stack.peek().equals("_") || stack.peek().equals("*") || stack.peek().equals("/"))) {
postfix.add(stack.pop());
}
stack.push(String.valueOf(exp.charAt(i)));
}
} else if (exp.charAt(i) == '(' || exp.charAt(i) == '[' || exp.charAt(i) == '{') {
stack.push(String.valueOf(exp.charAt(i)));
} else if (exp.charAt(i) == ')') {
while (!stack.isEmpty() && !stack.peek().equals("(")) {
postfix.add(stack.pop());
}
stack.pop();
} else if (exp.charAt(i) == ']') {
while (!stack.isEmpty() && !stack.peek().equals("[")) {
postfix.add(stack.pop());
}
stack.pop();
} else if (exp.charAt(i) == '}') {
while (!stack.isEmpty() && !stack.peek().equals("{")) {
postfix.add(stack.pop());
}
stack.pop();
} else {
StringBuilder num = new StringBuilder();
while (i < exp.length() && (exp.charAt(i) >= '0' && exp.charAt(i) <= '9')) {
num.append(exp.charAt(i));
++i;
}
--i;
postfix.add(num.toString());
}
}
while (!stack.isEmpty()) {
postfix.add(stack.pop());
}
return postfix;
}
}
发表于 2021-04-09 21:58:05
回复(3)
//利用了递归求解，程序十分简短
#include <iostream>
#include <string>
#include <sstream>
#include <deque>
using namespace std;
void addNum(deque<string>& Q,int num){
if(!Q.empty()){
int cur=0;
if(Q.back()=="*"||Q.back()=="/"){
string top=Q.back();
Q.pop_back();
stringstream ss(Q.back());
ss>>cur;
Q.pop_back();
num=top=="*"?(cur*num):(cur/num);
}
}
stringstream ss;
ss<<num;
Q.push_back(ss.str());
}
int getNum(deque<string>& Q){
int num=0,R=0;
string f("+");
while(!Q.empty()){
stringstream ss(Q.front());
ss>>num;
Q.pop_front();
R=(f=="+")?(R+num):(R-num);
if(!Q.empty()){
f=Q.front();
Q.pop_front();
}
}
return R;
}
int* value(string& s,int i){
deque<string> Q;
int pre=0;
while(i<s.length()&&s[i]!=')'&&s[i]!=']'&&s[i]!='}'){
if(s[i]>='0'&&s[i]<='9'){
pre=pre*10+s[i++]-'0';
}else if(s[i]!='('&&s[i]!='['&&s[i]!='{'){
addNum(Q,pre);
string ss;
ss+=s[i++];
Q.push_back(ss);
pre=0;
}else{
int* bra=NULL;
bra=value(s,i+1);
pre=bra[0];
i=bra[1]+1;
}
}
addNum(Q,pre);
int *R=new int[2];
R[0]=getNum(Q);
R[1]=i;
return R;
}
int main(){
string s;
while(cin>>s){
int *R=value(s,0);
cout<<R[0]<<endl;
}
return 0;
}
编辑于 2016-08-11 17:47:07
回复(1)
第一步，先考虑无括号的情况，先乘除后加减，遇到数字先压栈，如果下一个是乘号或除号，先出栈，和下一个数进行乘除运算，再入栈，最后就能保证栈内所有数字都是加数，最后对所有加数求和即可。
第二步，遇到左括号，直接递归执行第一步即可，最后检测到右括号，返回括号内的计算结果，退出函数，这个结果作为一个加数，返回上一层入栈。
# JAVA 版本
import java.io.*;
import java.util.Stack;
public class Main{
static int pos;
public static int compute(String s){
char ops = '+';
int num = 0;
Stack<Integer> val = new Stack<>();
int temp;
while(pos < s.length()){
if(s.charAt(pos) == '{' || s.charAt(pos) == '[' || s.charAt(pos) == '('){
pos++;
num = compute(s);
}
while(pos < s.length() && Character.isDigit(s.charAt(pos))){
num = num * 10 + s.charAt(pos) - '0';
pos++;
}
switch (ops){
case '+':
val.push(num);
break;
case '-':
val.push(-num);
break;
case '*':
temp = val.pop();
temp = temp * num;
val.push(temp);
break;
case '/':
temp = val.pop();
temp = temp / num;
val.push(temp);
break;
}
num = 0;
if(pos < s.length()) {
ops = s.charAt(pos);
if(s.charAt(pos) == '}' || s.charAt(pos) == ']' || s.charAt(pos) == ')'){
pos++;
break;
}
}
pos++;
}
int sum = 0;
while(!val.isEmpty()){
sum += val.pop();
}
return sum;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
pos = 0;
System.out.println(compute(str));
}
}
发表于 2021-03-03 11:17:45
回复(0)
原理参考博文：https://blog.csdn.net/Antineutrino/article/details/6763722
本质：将中缀表达式 转化为计算机容易计算的前缀表达式或后缀表达式
# 左括号右括号均弹出
# 最终S1为空栈，S2为只有加减乘除和数字的前缀表达式的栈
# 将S2进行运算和结果处理：从右往左扫描，碰到数字就入栈S3，碰到操作符就弹出S2栈顶的两个元素进行数***算然后将计算结果入栈S3，以此运算，S3栈留下的唯一数字即结果。
本质：将中缀表达式 转化为计算机容易计算的前缀表达式或后缀表达式
# 前缀表达式： 运算符栈S1【栈顶优先级更高】 + 存储中间结果栈S2【从右往左扫描中缀表达式数字】
简单过程描述：
# 优先级较高的操作符直接入栈S1，右括号直接入栈S1，遇到左括号则使使碰到右括号之前的操作符弹出S1放进S2# 左括号右括号均弹出
# 最终S1为空栈，S2为只有加减乘除和数字的前缀表达式的栈
# 将S2进行运算和结果处理：从右往左扫描，碰到数字就入栈S3，碰到操作符就弹出S2栈顶的两个元素进行数***算然后将计算结果入栈S3，以此运算，S3栈留下的唯一数字即结果。
# 本来考虑计算的优先顺序 圆括号> 中括号> 大括号，但是实质上不需要考虑这么多括号，把中括号大括号都替代成圆括号
import collections
def cat(exe_in):
limao = exe_in.replace('{', '(').replace('}', ')').replace('[', '(').replace(']', ')')
puc = [i for i in limao.strip()]
# print(puc)
# 如果碰到负数，在负数前加0
puc_copy = []
tmp = [] # 临时存储数字以合并个位数以上的数字
if puc[0] == '-':
puc_copy.append('0')
puc_copy.append('-')
elif puc[0].isdigit():
tmp.append(puc[0])
else:
puc_copy.append(puc[0])
# 十位数以上数字字符串合并
for i in range(1, len(puc)+1):
# print(puc[i])
if i < len(puc):
if puc[i] == '-' and puc[i - 1] == '(':
puc_copy.append('0')
puc_copy.append('-')
elif puc[i].isdigit():
tmp.append(puc[i])
elif tmp:
# print(tmp)
combine = ''.join(tmp)
puc_copy.append(combine)
puc_copy.append(puc[i])
tmp = []
else:
puc_copy.append(puc[i])
else:
if tmp: # 表达式末尾的数字字符串
combine = ''.join(tmp)
puc_copy.append(combine)
return puc_copy
def exe_transfer(exep):
# 创建字典进行优先级比较
coll_dict = collections.OrderedDict()
coll_dict = {'+': 5, '-': 5, '*': 4, '/': 4, '{': 3, '}': 3, '[': 2, ']': 2, '(': 1, ')': 1}
# 中缀表达式转化为前缀表达式
# 运算符栈S1【栈顶优先级更高】 + 存储中间结果栈S2【从右往左扫描中缀表达式数字】
exep.reverse()
S1, S2 = [], []
for i in exep:
# print('-----------')
# print(i)
# print(S1)
# print(S2)
# 判断字符串是否为数字
if i.isdigit():
S2.append(int(i))
# 操作符
else:
if S1 == []&nbs***bsp;S1 == ')': # 如果S1为空或者右括号直接入栈
S1.append(i)
elif S1[-1] == ')': # 如果S1栈顶为右括号直接入栈
S1.append(i)
elif i == '(': # 左括号带走右括号，并将他们之间的值推入S2
for j in range(len(S1) - 1, -1, -1):
if S1[j] != ')':
S2.append(S1[j])
S1.pop()
else:
S1.pop()
break
elif coll_dict[i] <= coll_dict[S1[-1]]: # 如果即将入栈的优先级较高直接入栈
S1.append(i)
# 有点小问题
else: # 如果即将入栈的优先级较低
S2.append(S1[-1])
S1.pop()
for j in range(len(S1)+1):
if S1 == []:
S1.append(i)
break
if S1[-1] == ')':
S1.append(i)
break
if coll_dict[i] > coll_dict[S1[-1]]:
S2.append(S1[-1])
S1.pop()
else:
S1.append(i)
break
# S1剩余部分
for k in range(len(S1)):
S2.append(S1[-1])
S1.pop()
# 返回前缀表达式
return S2
# S2计算函数
# 从右往左扫，碰到数字就入栈，碰到操作符就弹出栈顶的两个元素进行计算然后将计算结果入栈
def exe_cacul(prefix):
S3 = []
for i in prefix:
# print(i)
if i == '+'&nbs***bsp;i == '-'&nbs***bsp;i == '*'&nbs***bsp;i == '/':
if i == '+':
answer = S3[-1]+S3[-2]
elif i == '-':
answer = S3[-1] - S3[-2]
elif i == '*':
answer = S3[-1] * S3[-2]
else:
answer = S3[-1] / S3[-2]
S3.pop()
S3.pop()
S3.append(answer)
else: # 数字直接入栈
S3.append(i)
# print(S3)
return S3[0]
if __name__ == '__main__':
exe_in = input()
puc_copy = cat(exe_in)
# print(puc_copy)
prefix = exe_transfer(puc_copy)
# print(prefix)
print(int(exe_cacul(prefix)))
发表于 2020-09-10 17:20:07
回复(0)
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class Main {
private static Stack<Character> stack = new Stack<>();
private static StringBuilder postFix = new StringBuilder();
private static ArrayList<Integer> digitCnt = new ArrayList<>();
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
while (sc.hasNext()) {
String str = sc.next();
String postFix = trans(str);
int res = cal(postFix);
System.out.println(res);
}
}
//中缀表达式转成后缀表达式
static String trans(String inFix){
String newInFix = inFix.replace('{', '(') //都换成小括号
.replace('}', ')')
.replace(']', ')')
.replace('[', '(');
char[] chars = newInFix.toCharArray();
for (int i = 0; i < chars.length; ++i){
if (Character.isDigit(chars[i])){
int temp = 0;
//加上i < chars.length,否则数组越界
while (i < chars.length && Character.isDigit(chars[i])) {
postFix.append(chars[i]);
++i;
++temp;
}
--i;
digitCnt.add(temp);
}else if (chars[i] == '('){
stack.push(chars[i]);
}else if (chars[i] == '+' || chars[i] == '-'){
if (chars[i] == '-' && chars[i - 1] == '('){
postFix.append('0');
digitCnt.add(1);
}
while (!stack.isEmpty() && (stack.peek() == '*' || stack.peek() == '/' || stack.peek() == '+' || stack.peek() == '-')){
postFix.append(stack.peek());
stack.pop();
}
stack.push(chars[i]);
}else if (chars[i] == '*' || chars[i] == '/'){
while (!stack.isEmpty() && (stack.peek() == '*' || stack.peek() == '/')){
postFix.append(stack.peek());
stack.pop();
}
stack.push(chars[i]);
}else {
while (!stack.isEmpty() && stack.peek() != '('){
postFix.append(stack.peek());
stack.pop();
}
stack.pop();
}
}
while (!stack.isEmpty()){
postFix.append( stack.pop());
}
return postFix.toString();
}
//计算后缀表达式的值
static int cal(String postFix){
int index = 0;
Stack<Integer> stack1 = new Stack<>();
char[] chas = postFix.toCharArray();
for (int i = 0; i < chas.length; i++) {
if (Character.isDigit(chas[i])){
int total = 0;
int cnt = digitCnt.get(index);
while (cnt-- > 0){
total = 10 * total + (chas[i++] - '0');
}
--i;
stack1.push(total);
++index;
}else {
int num1 = stack1.peek();
stack1.pop();
int num2 = stack1.peek();
stack1.pop();
if (chas[i] == '+'){
stack1.push(num1 + num2);
}else if (chas[i] == '-'){
stack1.push(num2 - num1);
}else if (chas[i] == '*'){
stack1.push(num1 * num2);
}else {
stack1.push(num2 / num1);
}
}
}
return stack1.peek();
}
}
编辑于 2019-06-18 20:28:24
回复(1)
javascript 不用 eval() 解法，正则表达式绕了我好久，欢迎改进。
while(line=readline()){
var str = line.trim();var str = str.replace(/[\{\[]/g,"(").replace(/[\}\]]/g,")");
console.log(cal(str));
}
function cal(str){
var reg = /\(([^\(\)]+)\)/g;
while(reg.test(str)){
str = str.replace(reg,function($1,$2){
return cal2($2);
})
}
return cal2(str);
}function cal2(str){
var arr = [];
var sub = "";
for(var i = 0; i < str.length; i++){
if(/[\+\*\/-]/.test(str[i]) && !(/[\+\*\/-]/.test(str[i-1]))){
arr.push(sub);
sub = "";
arr.push(str[i]);
}else{
sub += str[i];
}
}
arr.push(sub);
var temp = [];
var result = [];
for(var i = 0; i < arr.length; i++){
if(/[\*\/]/.test(arr[i])){
var num1 = Number(temp.pop());
var num2 = Number(arr[i+1]);
if(arr[i] == "*"){
temp.push(num1*num2);
}else{
temp.push(num1/num2);
}
i++;
}else{
temp.push(arr[i]);
}
}
for(var i = 0; i < temp.length; i++){
if(/[\+-]/.test(temp[i])){
var num1 = Number(result.pop());
var num2 = Number(temp[i+1]);
if(temp[i] == "+"){
result.push(num1+num2);
}else{
result.push(num1-num2);
}
i++;
}else{
result.push(temp[i]);
}
}
return result[0];
}
发表于 2018-08-06 20:50:22
回复(1)
#include<iostream>
#include<stack>
#include<vector>
#include<string>
using namespace std;
//先转为逆波兰表达式再求值
class Solution {
public:
int evaluateExpression(vector<string> &expression) {
if (expression.empty()) return 0;
vector<string> op; //符号栈
vector<int> exp; //结果栈
for (unsigned int i = 0; i < expression.size(); ++i)
{//逐个扫描
if (expression[i] == "+" || expression[i] == "-")
{//处理"+","-"
if (op.size() == 0)
op.push_back(expression[i]);
else {//满足以下情况一直出栈
while (op.size() != 0 && (op[op.size() - 1] == "+" || op[op.size() - 1] == "-" || op[op.size() - 1] == "*" || op[op.size() - 1] == "/"))
{
string s = op.back();
op.pop_back();
int op2 = exp.back();
exp.pop_back();
int op1 = exp.back();
exp.pop_back();
if (s == "+") exp.push_back(op1 + op2);
else if (s == "-") exp.push_back(op1 - op2);
else if (s == "*") exp.push_back(op1 * op2);
else exp.push_back(op1 / op2);
}
op.push_back(expression[i]);
}
}//end +,-
else if (expression[i] == "*" || expression[i] == "/")
{//处理*,/
if (op.size() == 0)
op.push_back(expression[i]);
else if (op[op.size() - 1] == "*" || op[op.size() - 1] == "/")
{
string s = op.back();
op.pop_back();
int op2 = exp.back();
exp.pop_back();
int op1 = exp.back();
exp.pop_back();
if (s == "*") exp.push_back(op1 * op2);
else exp.push_back(op1 / op2);
op.push_back(expression[i]);
}
else
op.push_back(expression[i]);
}//end *,/
else if (expression[i] == "(") {
op.push_back(expression[i]);
}
else if (expression[i] == ")")
{//处理右括号
while (op.back() != "(")
{
string s = op.back();
op.pop_back();
int op2 = exp.back();
exp.pop_back();
int op1 = exp.back();
exp.pop_back();
if (s == "+") exp.push_back(op1 + op2);
else if (s == "-") exp.push_back(op1 - op2);
else if (s == "*") exp.push_back(op1 * op2);
else exp.push_back(op1 / op2);
}
op.pop_back();
}//end )
else
{//处理数字
exp.push_back(atoi(expression[i].c_str()));
}//done
}//end if
while (!op.empty())
{
string s = op.back();
op.pop_back();
int op2 = exp.back();
exp.pop_back();
int op1 = exp.back();
exp.pop_back();
if (s == "+") exp.push_back(op1 + op2);
else if (s == "-") exp.push_back(op1 - op2);
else if (s == "*") exp.push_back(op1 * op2);
else exp.push_back(op1 / op2);
}
if (exp.empty()) return 0;
return exp[0];
}
};
void preDeal(vector<string>& res, string str) {
for (int i = 0; i < str.size();++i) {
if (str[i] == '+' || str[i] == '*' ||
str[i] == '/' || str[i] == '(' || str[i] == ')')
res.push_back(str.substr(i, 1));
else if (str[i] == '-') {
if (i == 0 || (!isalnum(str[i - 1]) && str[i - 1] != ')')) res.push_back("0");
res.push_back("-");
}
else if (str[i] == '{' || str[i] == '[')
res.push_back("(");
else if (str[i] == '}' || str[i] == ']')
res.push_back(")");
else {//digit(s?)
int j = 1;
while (i + j < str.size() && isalnum(str[i + j])) ++j;
res.push_back(str.substr(i, j));
i += j - 1;
}
}
}
int main() {
string str;
Solution s;
while (getline(cin, str)) {
vector<string> tmp;
preDeal(tmp, str);
//for (auto s : tmp) cout << s << " ";
cout << s.evaluateExpression(tmp) << endl;
}
return 0;
}
发表于 2017-03-17 15:00:00
回复(0)
import java.util.Scanner;
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
public class Main{
public static void main(String[] args) throws Exception{
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
String input = scanner.nextLine();
ScriptEngineManager manager = new ScriptEngineManager();
ScriptEngine engine = manager.getEngineByName("js");
Object result = engine.eval(input);
System.out.println(result.toString());
}
scanner.close();
}
}
这个可能是最简单的java解法，评估为js字符串求解。
发表于 2021-04-11 11:39:32
回复(3)
投机取巧，利用js的eval（）函数，但是只能识别圆括号，所以需要替换下。
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws ScriptException {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str = sc.nextLine().replaceAll("\\{","(").replaceAll("\\[","(")
.replaceAll("}",")").replaceAll("]",")");
ScriptEngineManager manager = new ScriptEngineManager();
ScriptEngine se = manager.getEngineByName("js");
Object o = se.eval(str);
System.out.println(o);
}
}
}
发表于 2021-12-20 17:48:38
回复(1)
import re
a = input()
b = re.sub(r'\{|\[', '(', a)
c = re.sub(r'\}|\]', ')', b)
print(int(eval(c)))
发表于 2022-02-28 00:54:22
回复(0)
这题真的简单？反正我感觉这是我写过最杂乱的代码，毫无章法已经放飞自我了😐😐😑。还好本地调试后提交oj一次过。
import java.util.Scanner;
import java.util.Stack;
/**
* @author Yuliang.Lee
* @version 1.0
* @date 2021/9/23 18:37
* 四则运算：
输入一个表达式（用字符串表示），求这个表达式的值。
保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。
* 解题思路：（栈、递归）
第一步，先考虑无括号的情况，先乘除后加减，这个用栈很容易解决，遇到数字先压栈，如果下一个是乘号或除号，先出栈，和下一个数进行乘除运算，再入栈，最后就能保证栈内所有数字都是加数，最后对所有加数求和即可。
（注：将所有的减号都看成是负数，乘除则出栈运算后再将结果入栈，所以最后数字栈中的所有元素之间的运算符必定都是加号）
第二步，遇到左括号，直接递归执行第一步即可，最后检测到右括号，返回括号内的计算结果，退出函数，这个结果作为一个加数，返回上一层入栈。
* 示例
输入：3+2*{1+2*[-4/(8-6)+7]}
输出：25
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String expr = in.nextLine();
System.out.println(calculate(expr, 0));
}
}
public static String calculate(String expr, int index) {
// 数字栈（包含负数）
Stack<Integer> numbers = new Stack<>();
// 考虑有负数和减号的情况
boolean negative = false;
// 考虑有多位数的情况
StringBuilder tmp = new StringBuilder();
// flag为1的时候即运算符为乘除时，等待运算；为0才可以允许本趟的数字压栈
int flag = 0;
char op = ' ';
for (int i = index; i < expr.length(); i++) {
char ch = expr.charAt(i);
if (ch >= '0' && ch <= '9') {
tmp.append(ch);
}
else {
if (tmp.length() > 0) {
// 数字入栈
if (flag == 0 ) {
numbers.push(Integer.parseInt(negative ? ('-' + tmp.toString()) : tmp.toString()));
tmp.delete(0, tmp.length());
negative = false;
}
// 进行乘除运算
else {
int a = numbers.pop();
int b = Integer.parseInt(negative ? ('-' + tmp.toString()) : tmp.toString());
switch (op) {
case '*':
numbers.push(a * b);
break;
case '/':
numbers.push(a / b);
break;
default:
break;
}
tmp.delete(0, tmp.length());
negative = false;
flag = 0;
op = ' ';
}
}
// 处理本次字符
if (ch == '-') {
negative = true;
} else if (ch == '*' || ch == '/') {
flag = 1;
op = ch;
} else if (ch == '{' || ch == '[' || ch == '(') {
// 递归调用函数
String[] middleResult = calculate(expr, i+1).split(",");
// 处理递归返回的结果
tmp.append(middleResult[0]);
i = Integer.parseInt(middleResult[1]);
} else if (ch == '}' || ch == ']' || ch == ')') {
// 计算函数的结果值
int sum = 0;
for (Integer number : numbers) {
sum += number;
}
// 返回递归值
return sum + "," + i;
}
}
}
// 处理最后一次的数字和运算
if (tmp.length() != 0) {
int b = Integer.parseInt(negative ? ('-' + tmp.toString()) : tmp.toString());
if (flag == 1) {
int a = numbers.pop();
switch (op) {
case '*':
numbers.push(a * b);
break;
case '/':
numbers.push(a / b);
break;
default:
break;
}
} else {
numbers.push(b);
}
}
// 返回最终的结果值
int result = 0;
for (Integer number : numbers) {
result += number;
}
return result + "" ;
}
}
发表于 2021-09-23 20:33:28
回复(0)
问题信息
难度：
376条回答
3178收藏
45959浏览
通过挑战的用户
查看代码-
2023-03-12 23:17:55 -
2023-02-14 15:12:51 -
2022-11-16 14:17:46
-
2022-09-16 17:30:30 -
2022-09-16 17:01:45
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
