第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-156 表达式计算
前言
这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。
表达式计算
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。
输入格式
输入一行，包含一个表达式。
输出格式
输出这个表达式的值。
样例输入
1-2+3*(4-5)
样例输出
-4
数据规模和约定
表达式长度不超过100，表达式运算合法且运算过程都在int内进行。
题解：
C语言
#include<stdio.h> #include<stdlib.h> #include<math.h> #define MAXSIZE 101 void Translate(char str[], char exp[]) { char stack[MAXSIZE]; int i = 0, k = 0, top = -1; while (str[i] != '\0') { if (str[i] == '(') { stack[++top] = str[i++]; } else if (str[i] == ')') { while (top >= 0 && stack[top] != '(') { exp[k++] = stack[top--]; } if (top < 0) { exp[k++] = '\0'; return ; } top--; i++; } else if (str[i] == '+' || str[i] == '-') { while (top >= 0 && stack[top] != '(') { exp[k++] = stack[top--]; } stack[++top] = str[i++]; } else if (str[i] == '*' || str[i] == '/') { while (top >= 0 && (stack[top] == '*' || stack[top] == '/')) { exp[k++] = stack[top--]; } stack[++top] = str[i++]; } else { while ((str[i] >= '0' && str[i] <= '9')) { exp[k++] = str[i++]; } exp[k++] = '#'; } } while (top >= 0) { if (stack[top] == '(') { exp[k++] = '\0'; return ; } exp[k++] = stack[top--]; } exp[k++] = '\0'; } int CompValue(char *exp) { char tempStr[MAXSIZE]; int stack[MAXSIZE]; int i = 0, k = 0, top = -1; while (exp[i] != '\0') { if (exp[i] >= '0' && exp[i] <= '9') { k = 0; while (exp[i] != '#') { tempStr[k++] = exp[i++]; } tempStr[k] = '\0'; stack[++top] = atoi(tempStr); i++; } else { switch (exp[i++]) { case '+' : stack[top-1] += stack[top]; break; case '-' : stack[top-1] -= stack[top]; break; case '*' : stack[top-1] *= stack[top]; break; case '/' : if (stack[top] != 0) { stack[top-1] /= stack[top]; } else { return 0; } break; } top--; } } return stack[top]; } int main() { char buf[MAXSIZE],buf1[MAXSIZE]; scanf("%s",buf); Translate(buf,buf1); printf("%d",CompValue(buf1)); return 0; }
C++语言
#include<iostream> //#include<stdio.h> #include<stdlib.h> using namespace std; typedef int ETlemType; typedef int status; #define MAXSIZE 15//顺序栈的最大长度 #define OK 1 #define ERROR 0 #define OVERSTACK 0//满栈溢出 typedef struct Stack1 { ETlemType date[MAXSIZE]; int top; //int stacksiza;//栈的最大长度 }SqStack; int Compare(char ch,char b); status InitStack(SqStack &s);//建立空栈 status Push(SqStack &s,ETlemType e);//进栈 status StackEmpty( SqStack s );//判断栈是否为空 status Pop(SqStack &s,ETlemType &e);//出栈 status GetTop(SqStack s, ETlemType &e);//取栈顶元素 int Operation(char ch,int ch1,int ch2);//运算 int houzhi(int Out[],int pd[],char a[],SqStack s);//转换为后缀表达式,pd用于判断是数字还是运算符.,同事时返回长度 int zhuanhuan(char a[],char b[]); //int zhuanhuan(char a[],char b[]); int main() { int i=0,j=0; char a[1000]; int Out[500],pd[500],ch; int length=0; SqStack s;//数字栈，运算符栈 cin>>a; InitStack(s); length=houzhi(Out,pd,a,s); i=0; int ch1=0,ch2=0; do { if(pd[i]==1) { ch=Out[i]; Push(s,ch);//入栈 //cout<<ch<<endl; } else { Pop(s,ch1); Pop(s,ch2); Push(s,Operation((char)Out[i],(int)ch1,(int)ch2)); } i++; }while(i<length); cout<<s.date[0]<<endl; return 0; } int houzhi(int Out[],int pd[],char a[],SqStack s)//转换为后缀表达式,pd用于判断是数字还是运算符 { int ch,sum; int i=0,j=0; do { if(a[i]<='9' && a[i]>='0') { sum=0; while(a[i]<='9' && a[i]>='0') {sum=sum*10+a[i]-'0';i++;} i--; Out[j++]=sum;pd[j-1]=1; } else if(a[i]==')'){ do { Pop(s,ch); if(ch=='(')break; Out[j++]=ch;pd[j-1]=0; }while(1); } else if(a[i]=='(')Push(s,a[i]); else if(a[i]=='\0'){//cout<<"111"<<endl; do { Pop(s,ch); Out[j++]=ch; pd[j-1]=0;//cout<<"333"<<endl; }while(s.top!=-1);// break;//运算符移位完成 } else{ if(StackEmpty(s)) {//如果栈不为空 GetTop(s,ch); if( Compare(ch,a[i])>0 && ch!='(')//栈顶元素优先级高则输出 {//cout<<"111"<<endl;//p; while(Compare(ch,a[i])>0 && ch!='(' && StackEmpty(s) ) {Pop(s,ch);Out[j++]=ch;pd[j-1]=0;GetTop(s,ch);}//[[[[[[[[[[ } } Push(s,a[i]); } i++; }while(1);//运算符中缀改为后缀 //Out[j]=0;//puts(Out);//实验 /*for(i=0;i<j;i++) { cout<<(char)Out[i]<<" "; } cout<<endl;*/ return j; } int Compare(char ch,char b) { switch(b) { case '+':return 1;//优先级低于ch case '-':if(ch!='*' && ch=='/')return -1;//b的优先级不低于ch else return 1;//优先级低于ch case '/': case '*':return -1;//b处于优先级最高位 default:break; } return 1; } status InitStack(SqStack &s)//建立空栈 { s.top=-1; return OK; } status Push(SqStack &s,ETlemType e)//进栈 { if(s.top>=MAXSIZE-1)return ERROR; s.top++; s.date[s.top]=e; return OK; } status StackEmpty( SqStack s )//判断栈是否为空 { if(s.top<=-1)return ERROR; return OK; } status Pop(SqStack &s,ETlemType &e)//出栈 { if(s.top<=-1)return ERROR; e=s.date[s.top]; s.top--; return OK; } status GetTop(SqStack s, ETlemType &e)//取栈顶元素 { if(s.top==-1)return ERROR; e=s.date[s.top]; return OK; } int Operation(char ch,int ch1,int ch2) { switch(ch) { case '+':return (ch2+ch1); case '-':return (ch2-ch1); case '*':return (ch2*ch1); case '/':return (ch2/ch1); default:return -1 ;break; } }
Java语言
在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder expression = new StringBuilder("(" + br.readLine() + ")"); // 表达式，在输入的表达式两边加上括号 StringBuilder temp = new StringBuilder(); // 存放临时表达式，即每次存放的都是任意一个括号中的子表达式 while (true) { int frontBrackets = expression.lastIndexOf("("); // 从表达式后边开始搜索，找到最后一个"(" int backBrackets = expression.indexOf(")", frontBrackets); // 从最后一个"("的位置开始往后搜索，找到与之对应的")" if (frontBrackets == -1) { break; // 若再无表达式需要计算，即expression只有一个整数时，跳出循环 } temp.append(expression.substring(frontBrackets + 1, backBrackets)); // 将此括号中的表达式存入temp expression.delete(frontBrackets, backBrackets + 1); // 在原始表达式中将括号连同其中的表达式删除 for (int i = 0; i < temp.length(); i++) { // 从子表达式中找出运算符，根据运算原则，先乘除后加减 if (temp.charAt(i) == '*') { // 若找到 "*" ，调用calculation进行运算 calculation(temp, '*', i); i = 0; // 运算完后，i清零，方便下一次从开始位置继续寻找乘除运算符 } if (temp.charAt(i) == '/') { calculation(temp, '/', i); i = 0; } } for (int i = 0; i < temp.length(); i++) { // 找完乘除运算符后，开始找加减运算符 if (temp.charAt(i) == '+') { calculation(temp, '+', i); i = 0; } if (temp.charAt(i) == '-') { calculation(temp, '-', i); i = 0; } } expression.insert(frontBrackets, temp); // 运算完后，将结果插入在刚才删除的括号位置，构成新的表达式，继续循环计算 temp.delete(0, temp.length()); // 将temp清空，方便下一个表达式计算 } System.out.println(expression); // 输出结果 } /** * 计算表达式 * * @param src * 表达式 * @param op * 操作符 * @param location * 操作符在表达式中的位置 */ private static void calculation(StringBuilder src, char op, int location) { int x = 0; // 操作数1 int y = 0; // 操作数2 int sum = 0;// sum = x (op) y String check = "0123456789+-"; // 检测运算符两边的内容是否为其中数组或者正数或负数 StringBuilder temp = new StringBuilder(); // 存放运算符两边的字符 if (location == 0) return; // 若遇到子表示其中只有加减运算符这种情况，且遇到的第一个运算符其实是想表示一个正数或者负数的符号，则函数返回，继续寻找下一个运算符 int k = 0; // 搜索操作符左右两边的数 for (k = location - 1; k >= 0 && check.contains(src.charAt(k) + ""); k--) { // 从运算符左边一个位置开始往前搜索，找到第一个操作数 try { // 若数字前边有两个运算符，第一个是为了与前边的数相连，第二个是为了表示这个数的正负，则跳出循环，执行后面的语句 // 比如： // 5+(7+-5*+10)，搜索到5前边时，先搜索到"-",发现前边还有一个"+"，此时temp中没有运算符，则继续执行，当搜索到"+"时，发现前边没有运算符了，就跳出循环 if ((src.charAt(k) == '+' || src.charAt(k) == '-') && (src.charAt(k - 1) != '+' || src.charAt(k - 1) != '-')) break; if (temp.charAt(0) == '+' || temp.charAt(0) == '-') break; } catch (Exception e) { // e.printStackTrace(); //不输出异常，满足题目输出要求 } temp.insert(0, src.charAt(k)); // 每次都是从temp的开始位置插入内容，保证逆向搜索的内容能按照正常的顺序存入temp src.deleteCharAt(k); // 删除运算符前边的那个数字，若有正负号，也一并删除 } x = Integer.parseInt(temp.toString()); // 将搜索到的此数存入x temp.delete(0, temp.length()); // 将temp清空 for (k = k + 2; k < src.length() && check.contains(src.charAt(k) + "");) { // 从运算符右边一个位置开始往后搜索，找到第二个操作数，加2是因为上边的循环语句在结束时自减了一次 if ((src.charAt(k) == '+' || src.charAt(k) == '-') && (temp.length() != 0)) break; temp.append(src.charAt(k)); src.deleteCharAt(k); } y = Integer.parseInt(temp.toString()); temp.delete(0, temp.length()); switch (op) { case '+': sum = x + y; src.deleteCharAt(k - 1); // 删除运算符 src.insert(k - 1, sum + ""); // 将结果存入src的操作符位置（此时操作符两边的数已经从src中删除，所以插入此位置相当于用结果代替子表达式，方便下一次运算） break; case '-': sum = x - y; src.deleteCharAt(k - 1); src.insert(k - 1, sum + ""); break; case '*': sum = x * y; src.deleteCharAt(k - 1); src.insert(k - 1, sum + ""); break; case '/': sum = x / y; src.deleteCharAt(k - 1); src.insert(k - 1, sum + ""); break; default: break; } } }
Python语言
相对简洁，但是需要对Python的一些语法很了解，特别是列表推导式的熟悉。
这才是神奇。
print(eval(input()))
总结
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
