河南省第九届ACM 表达式求值

忘是亡心i 2023-06-13 11:21 14阅读 0赞

题目描述  
假设表达式定义为:

1.  一个十进制的正整数 X 是一个表达式。
2.  如果 X 和 Y 是 表达式，则 X+Y, X\*Y 也是表达式; \*优先级高于+.
3.  如果 X 和 Y 是 表达式，则 函数 Smax(X,Y)也是表达式,其值为:先分别求出 X ,Y  
    值的各位数字之和，再从中选最大数。  
    4．如果 X 是 表达式，则 （X）也是表达式。  
    例如:  
    表达式 12\*(2+3)+Smax(333,220+280) 的值为 69。  
    请你编程，对给定的表达式，输出其值。  
    输入  
    第一行： T 表示要计算的表达式个数 （ 1 ≤ T ≤ 10 1 \\le T \\le 10 1≤T≤10）  
    接下来有 T 行， 每行是一个字符串，表示待求的表达式，长度<=1000  
    输出  
    对于每个表达式，输出一行，表示对应表达式的值。  
    样例输入 Copy  
    3  
    12+2*3  
    12*(2+3)  
    12\*(2+3)+Smax(333,220+280)  
    样例输出 Copy  
    18  
    60  
    69

package ACM2016;
    import java.util.Scanner;
    import java.util.Stack;
    public class A { 
    	public static void main(String[] args) { 
    		Stack dsta =new Stack(); 
    		Stack osta =new Stack(); 
    		int T,i,j;
    		Scanner sc=new Scanner(System.in);
    		T=sc.nextInt();
    		sc.nextLine();
    		while((T--)>0)
    		{ 
    			String str=sc.nextLine();
    			str="("+str+")";
    			char s[]=str.toCharArray();
    			int len=s.length-1;
    			for(i=0;i<=len;i++)
    			{ 
    				if(s[i]=='(')
    					osta.push(s[i]);
    				else if(s[i]=='S')
    				{ 
    					osta.push('(');//压入一个左括弧 
    					i+=3;
    				}
    				else if(s[i]>='0' && s[i]<='9')
    				{ 
    					int v=0;
    					while(s[i]>='0' && s[i]<='9')
    						v=v*10+(s[i++]-'0');
    					i--;
    					dsta.push(v);
    				}
    				else if(s[i]=='+')
    				{ 
    					while((char)osta.peek()!='(' && (char)osta.peek()!=',')
    					{ 
    						int a=(int)dsta.peek(); dsta.pop();
    						int b=(int)dsta.peek(); dsta.pop();
    						int c = 0;
    						switch((char)osta.peek())
    						{ 
    							case '+':c=b+a;break;
    							case '*':c=b*a;break;
    						}
    						dsta.push(c);
    						osta.pop();
    					}
    					osta.push(s[i]);
    				}
    				else if(s[i]=='*')
    				{ 
    					if((char)osta.peek()=='*')
    					{ 
    						int a=(int)dsta.peek(); dsta.pop();
    						int b=(int)dsta.peek(); dsta.pop();
    						dsta.push(b*a);
    						osta.pop();
    					}
    					osta.push(s[i]);
    				}
    				else if(s[i]==')' || s[i]==',')//遇到逗号及时求值 
    				{  //当遇到 ','时，就把Smax的前半部分表达式的值求出来 
    					while((char)osta.peek()!='(')
    					{ 
    						int a=(int)dsta.peek(); dsta.pop();
    						int b=(int)dsta.peek(); dsta.pop();
    						int c = 0,suma=0,sumb=0;
    						switch((char)osta.peek())
    						{ 
    							case '+':c=b+a;break;
    							case '*':c=b*a;break;
    							case ',':{ 
    							//逐位分割求和 
    								while(b!=0)
    								{ 
    									sumb+=b%10; b/=10;
    								}
    								while(a!=0)
    								{ 
    									suma+=a%10; a/=10;
    								}
    								c=Math.max(suma,sumb);
    								break;
    							}
    						}
    						dsta.push(c);
    						osta.pop();
    					}
    					osta.pop();
    					if(s[i]==',')//求完值之后，把逗号压入栈内，以便后半部分Smax表达式的求值 
    						osta.push(s[i]);
    				}
    			}
    			System.out.println((int)dsta.peek());
    			dsta.pop();
    		}
    	}
    
    }