中缀表达式求值
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
public class Test21 {
static Stack<Integer> num=new Stack<>();
static Stack<Character> op=new Stack<>();
static Map<Character,Integer> pr=new HashMap<Character,Integer>(){
{
put('+',1);
put('-',1);
put('*',2);
put('/',2);
}
};
public static void main(String[] args) {
//中缀表达式求值
Scanner sc=new Scanner(System.in);
String s=sc.nextLine();
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
if(Character.isDigit(ch)){
int x=0;int j=i;
while (j < s.length() && Character.isDigit(s.charAt(j))) {
x=x*10+s.charAt(j++)-'0';
}
j=i-1;
num.push(x);
}else if(ch=='('){
op.push(ch);
}else if(ch==')'){
while(op.peek()!='('){
eval();
}
//将左括号弹出
op.pop();
}else{
//对于其他运算符
while(!op.isEmpty()&&op.peek()!='('&&pr.get(ch)<=pr.get(op.peek())){
//优先级更高的先计算
eval();
}
op.push(ch);
}
}
while (!op.isEmpty()) {
eval();
}
System.out.println(num.peek());
}
public static void eval(){
int b=num.pop();
int a=num.pop();
char c=op.pop();
int res=0;
if(c=='+'){
res=a+b;
}else if(c=='-'){
res=a-b;
}else if(c=='*'){
res=a*b;
}else if(c=='/'){
res=a/b;
}
num.push(res);
}
}
有效的括号字符串
有效的括号字符串
通过双栈的方式，优先将左括号进行匹配，然后与星号进行匹配，如果对应的星号不能匹配，输出false
最后将剩下的左括号与星号进行匹配，如果最后能够将所有的左括号进行匹配，返回true
否则最后剩下左括号不能匹配，返回false
class Solution {
public boolean checkValidString(String s) {
//通过两个栈的方式
Stack<Integer> stack01=new Stack<Integer>();
Stack<Integer> stack02=new Stack<Integer>();
//将对应的下标
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='('){
stack01.push(i);
}else if(s.charAt(i)=='*'){
stack02.push(i);
}else{
//对应的右括号
if(!stack01.isEmpty()){
stack01.pop();
}else if(!stack02.isEmpty()){
stack02.pop();
}else{
return false;
}
}
}
//最后如果对应的左括号栈不为空
while(!stack01.isEmpty()&&!stack02.isEmpty()){
int pos=stack01.peek();
int pos1=stack02.peek();
if(pos<pos1){
stack01.pop();
stack02.pop();
}else{
return false;
}
}
if(!stack01.isEmpty()){
return false;
}
return true;
}
}
方式二： 通过dp方式进行表达式判断
通过dp[i][j]表示对应的字符串[i:j]是否为合理的括号表达式
class Solution {
public boolean checkValidString(String s) {
int n=s.length();
boolean[][] dp=new boolean[n][n];//dp[i][j]表示区间[i:j]是否是有效的表达式
//对于所有的长度为1/2字符串进行判断
for(int i=0;i<n;i++){
if(s.charAt(i)=='*'){
dp[i][i]=true;
}
}
for(int i=1;i<n;i++){
if((s.charAt(i-1)=='('||s.charAt(i-1)=='*')&&(s.charAt(i)=='*'||s.charAt(i)==')')){
dp[i-1][i]=true;
}
}
for(int i=n-3;i>=0;i--){
for(int j=i+2;j<n;j++){
if((s.charAt(i)=='('||s.charAt(i)=='*')&&(s.charAt(j)==')'||s.charAt(j)=='*')){
dp[i][j]=dp[i+1][j-1];
}
// if(!dp[i][j]){
// for(int k=i;k<j;k++){
// dp[i][j]=dp[i][k]&&dp[k+1][j];
// if(dp[i][j]){
// break;
// }
// }
// }
for(int k=i;k<j&&!dp[i][j];k++){
dp[i][j]=dp[i][k]&&dp[k+1][j];
}
}
}
return dp[0][n-1];
}
}
为运算表达式设计优先级
通过递归方式+记忆化搜索
对每一个运算符进行递归运算dfs(),将运算符左右递归结果进行合并
public List<Integer> diffWaysToCompute(String input) {
if (input.length() == 0) {
return new ArrayList<>();
}
List<Integer> result = new ArrayList<>();
int num = 0;
//考虑是全数字的情况
int index = 0;
while (index < input.length() && !isOperation(input.charAt(index))) {
num = num * 10 + input.charAt(index) - '0';
index++;
}
//将全数字的情况直接返回
if (index == input.length()) {
result.add(num);
return result;
}
for (int i = 0; i < input.length(); i++) {
//通过运算符将字符串分成两部分
if (isOperation(input.charAt(i))) {
List<Integer> result1 = diffWaysToCompute(input.substring(0, i));
List<Integer> result2 = diffWaysToCompute(input.substring(i + 1));
//将两个结果依次运算
for (int j = 0; j < result1.size(); j++) {
for (int k = 0; k < result2.size(); k++) {
char op = input.charAt(i);
result.add(caculate(result1.get(j), op, result2.get(k)));
}
}
}
}
return result;
}
private int caculate(int num1, char c, int num2) {
switch (c) {
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
}
return -1;
}
private boolean isOperation(char c) {
return c == '+' || c == '-' || c == '*';
}
通过dp[i][j] 将所有的数放入list 将所有的运算符放入list
分数加减运算
class Solution {
public String fractionAddition(String expression){
List<Character> ops=new ArrayList<Character>();
for(int i=1;i<expression.length();i++){
if(expression.charAt(i)=='+'||expression.charAt(i)=='-'){
ops.add(expression.charAt(i));
}
}
List<Integer> nums1=new ArrayList<Integer>();
List<Integer> nums2=new ArrayList<>();
for (String s : expression.split("\\+")) {
for (String sub : s.split("-")) {
if(sub.length()>0){
String[] ss=sub.split("/");
nums1.add(Integer.parseInt(ss[0]));
nums2.add(Integer.parseInt(ss[1]));
}
}
}
if(expression.charAt(0)=='-'){
nums1.set(0,-nums1.get(0));
}
int com=nums2.get(0);
for(int i=1;i<nums2.size();i++){
com=lcm(com,nums2.get(i));
}
//分子累加起始
int start=nums1.get(0)*(com/nums2.get(0));
for(int i=1;i<nums1.size();i++){
if(ops.get(i-1)=='+'){
start+=nums1.get(i)*(com/nums2.get(i));
}else{
start-=nums1.get(i)*(com/nums2.get(i));
}
}
int c=gcd(Math.abs(com),Math.abs(start));
return String.valueOf(start/c)+"/"+String.valueOf(com/c);
}
public int lcm(int a,int b){
return a*b/gcd(a,b);
}
public int gcd(int a,int b){
if(b==0){
return a;
}
return a%b==0? b:gcd(b,a%b);
}
}
