保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’, ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。
数据范围:表达式计算结果和过程中满足 ,字符串长度满足
数据范围:表达式计算结果和过程中满足 ,字符串长度满足
输入一个算术表达式
得到计算结果
3+2*{1+2*[-4/(8-6)+7]}
25
//用python做(两句话),显然得不到练习的效果,有什么意思呢; //还是用C++写吧。 #include <iostream> #include <string.h> #include <stack> #include <vector> using namespace std; bool isHigh(char top_op,char InfixExp_op) //判断操作符的优先级; //top_op为栈顶操作符 //InfixExp_op为当前读入操作符 //如果栈顶操作符优先级高,则弹出栈顶操作符; //如果栈顶操作符优先级低,则压入当前读入操作符; { if ((top_op== '+')&&(InfixExp_op== '+')) return true; if ((top_op== '+')&&(InfixExp_op== '-')) return true; if ((top_op== '-')&&(InfixExp_op== '+')) return true; if ((top_op== '-')&&(InfixExp_op== '-')) return true; if ((top_op== '*')&&(InfixExp_op== '+')) return true; if ((top_op== '*')&&(InfixExp_op== '-')) return true; if ((top_op== '*')&&(InfixExp_op== '*')) return true; if ((top_op== '*')&&(InfixExp_op== '/')) return true; if ((top_op== '/')&&(InfixExp_op== '+')) return true; if ((top_op== '/')&&(InfixExp_op== '-')) return true; if ((top_op== '/')&&(InfixExp_op== '*')) return true; if ((top_op== '/')&&(InfixExp_op== '/')) return true; if (InfixExp_op== ')') return true; return false; } int main() { char str[5000]; while(cin>>str) { int len=strlen(str); stack<char> sta; vector<int> vec; vector<bool> vec_b; int sum=0; int flag=1; int flb=0;//两个相邻的数之间运算符的个数,挑负数; for(int i=0;i<len;++i) { if(i==0&&str[i]=='-')//把负号挑出来; { flag=-1; continue; } if(i>0&&str[i]=='-'&&flb==1)//把负号挑出来; { flag=-1; continue; } if(str[i]>='0'&&str[i]<='9') { sum=sum*10+(str[i]-'0'); if(!(str[i+1]>='0'&&str[i+1]<='9')) { sum*=flag; vec.push_back(sum); vec_b.push_back(true);//真为数,假为运算符的; sum=0; flag=1; flb=0; } } else { if(str[i]=='['||str[i]=='{') str[i]='('; if(str[i]==']'||str[i]=='}') str[i]=')'; if(str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/') ++flb; if (sta.empty()) //栈为空,压入操作符; sta.push(str[i]); else if(isHigh(sta.top(),str[i])) //栈顶操作符优先,比如栈顶为*,当前操作符为+,则弹出* { if (str[i]!= ')') //非闭括号; //弹出栈中操作符直到栈顶操作数优先级低于当前读入操作数; //压入当前读入操作符; { do { if(sta.top()!='('||sta.top()!=')') { vec.push_back(sta.top()); vec_b.push_back(false); } sta.pop(); }while((!sta.empty())&&(isHigh(sta.top(),str[i]))); sta.push(str[i]); } else //闭括号; { while((!sta.empty())&&(sta.top()!= '(')) //弹出直到开括号; { if(sta.top()!='('||sta.top()!=')') { vec.push_back(sta.top()); vec_b.push_back(false); } sta.pop(); } if ((!sta.empty())&&(sta.top()== '(')) sta.pop(); //弹出开括号; } } else if(!isHigh(sta.top(),str[i])) //中缀表达式中操作符优先; //比如栈顶为+,而当前读入*; { sta.push(str[i]); //压入当前读入操作符; } } } while(!sta.empty()) //把栈中剩余的操作符依次弹出; { if(sta.top()!='('||sta.top()!=')') { vec.push_back(sta.top()); vec_b.push_back(false); } sta.pop(); } while(!sta.empty()) sta.pop(); stack<int> sta_i; int mm=vec.size(); int res=0; /*for (int i=0;i<mm;++i)//测试用; { if (vec_b[i]) { cout<<vec[i]<<" "; } else { cout<<(char)vec[i]<<" "; } } cout<<endl;*/ for (int i=0;i<mm;++i) { if(vec_b[i]) { sta_i.push(vec[i]); } else { int t1=0; int t2=0; int t3=0; if(!sta_i.empty()) { t1=sta_i.top(); sta_i.pop(); } if (!sta_i.empty()) { t2=sta_i.top(); sta_i.pop(); } if(vec[i]==43) t3=t1+t2; else if(vec[i]==45) t3=t2-t1; else if(vec[i]==42) t3=t2*t1; else if(vec[i]==47) t3=t2/t1; sta_i.push(t3); } } if (!sta_i.empty()) res=sta_i.top(); cout<<res<<endl; while(!sta_i.empty()) sta_i.pop(); vec.clear(); } return 0; }
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
#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; }
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("异常数据,计算失败!"); } }
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; } }
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; } }
//利用了递归求解,程序十分简短 #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; }
第一步,先考虑无括号的情况,先乘除后加减,遇到数字先压栈,如果下一个是乘号或除号,先出栈,和下一个数进行乘除运算,再入栈,最后就能保证栈内所有数字都是加数,最后对所有加数求和即可。
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)); } }
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)))
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(); } }
}function cal2(str){
#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; }
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字符串求解。
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); } } }
import re a = input() b = re.sub(r'\{|\[', '(', a) c = re.sub(r'\}|\]', ')', b) print(int(eval(c)))
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 + "" ; } }