2 solutions
-
2
视频讲解:https://www.bilibili.com/video/BV1E44y1E7Jc?p=2&share_source=copy_web
#include<iostream> #include<string.h> #include<algorithm> #include<math.h> #include<vector> #include<map> #include<stack> using namespace std; typedef long long ll; const ll md=1e5; stack<ll> num; stack<char> op; map <char,ll> ma; ll a,b; int main(){ ma['+']=1; ma['*']=2; string s; cin>>s; for(int i=0;i<s.size();i++){ if(s[i]>='0'&&s[i]<='9'){ int x=0; while(s[i]>='0'&&s[i]<='9'){ x=x*10+s[i]-'0'; i++; } i--; num.push(x); } else{ if(op.empty())op.push(s[i]); else{ while(!op.empty()&&ma[op.top()]>=ma[s[i]]){ if(op.top()=='+'){ a=num.top(); num.pop(); b=num.top(); num.pop(); num.push((a+b)%md); } else{ a=num.top(); num.pop(); b=num.top(); num.pop(); num.push((a%md*b%md)%md); } op.pop(); } op.push(s[i]); } } } ll ans=0; while(num.size()>=2){ a=num.top(); num.pop(); b=num.top(); num.pop(); if(op.top()=='+'){ num.push((a+b)%md); op.pop(); } else{ num.push((a%md*b%md)%md); op.pop(); } } ans=num.top(); if(ans>=10000)cout<<ans%10000; else cout<<ans; return 0; }
-
1
浅写一个java的
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 in = new Scanner(System.in); String expression = in.nextLine();//注意表达式 List<String> infixExpressionList = toInfixExpressionList(expression); // System.out.println("中缀表达式对应的List=" + infixExpressionList); List<String> suffixExpreesionList = parseSuffExpressionList(infixExpressionList); // System.out.println("后缀表达式对应的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–] // String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76 // List<String> list = getListString(suffixExpression); int res = calculate(suffixExpreesionList); System.out.println(res % 10000); } public static List<String> parseSuffExpressionList(List<String> ls){ Stack<String> s1 = new Stack<>(); // Stack<String> s2 = new Stack<>(); List<String> s2 = new ArrayList<>(); for(String item : ls){ if(item.matches("\\d+")){ s2.add(item); }else if(item.equals("(")){ s1.push(item); }else if(item.equals(")")){ while(!s1.peek().equals("(")){ s2.add(s1.pop()); } s1.pop(); }else { while(s1.size() != 0 && Operation.getValue(s1.peek())>=Operation.getValue(item)){ s2.add(s1.pop()); } s1.push(item); } } while(s1.size() != 0){ s2.add(s1.pop()); } return s2; } public static List<String> toInfixExpressionList(String s){ List<String> list = new ArrayList<String>(); int i = 0; String str; char c; do{ if((c = s.charAt(i)) <48 || (c = s.charAt(i)) > 57){ list.add("" + c);//转换成字符串 i++; }else { str = ""; while( i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57){ str += c; i++; } list.add(str); } }while(i < s.length()); return list; } public static List<String> getListString(String suffixExpression) { String split[] = suffixExpression.split(" "); List<String> list = new ArrayList<>(); for (String element : split) { list.add(element); } return (list); } public static int calculate(List<String> ls) { Stack<String> stack = new Stack<String>(); for (String element : ls) { if (element.matches("\\d+")) { stack.push(element); } else { int num2 = Integer.parseInt(stack.pop()); int num1 = Integer.parseInt(stack.pop()); int res = 0; if (element.equals("+")) { res = (num1 + num2) % 10000; } else if (element.equals("-")) { res = (num1 - num2) % 10000; } else if (element.equals("*")) { res = (num1 * num2) % 10000; } else if (element.equals("/")) { res = (num1 / num2) % 10000; } else { throw new RuntimeException("运算符有误"); } stack.push("" + res); } } return Integer.parseInt(stack.pop()); } } class Operation{ private static int ADD = 1; private static int SUB = 1; private static int MUL = 2; private static int DIV = 2; public static int getValue(String operation){ int result = 0; switch(operation){ case "+": result = ADD; break; case "-": result = SUB; break; case "*": result = MUL; break; case "/": result = DIV; break; default: break; } return result; } }
- 1
Information
- ID
- 290
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 7
- Tags
- # Submissions
- 82
- Accepted
- 19
- Uploaded By