[Leetcode] Basic Calculator/Evaluate Expression 设计计算器/中缀表达式求值_Java_ThinkSAAS
[Leetcode] Basic Calculator/Evaluate Expression 设计计算器/中缀表达式求值
[Leetcode] Basic Calculator/Evaluate Expression 设计计算器/中缀表达式求值
内容来源： 网络
PHP开发框架
开发工具/编程工具
服务器环境
ThinkSAAS商业授权：
ThinkSAAS为用户提供有偿个性定制开发服务
ThinkSAAS将为商业授权用户提供二次开发指导和技术支持
让ThinkSAAS更好，把建议拿来。
开发客服微信所用知识：C语言，堆栈操作
算法思想来自慕课浙江大学《数据结构》陈老师，何老师
1.堆栈：&& &1.1 引子&& &&& &&& &一种数据结构，在函数调用，表达式求值等都有广泛的应用&& &&& &中缀表达式：a+b*c-d/e:生活中经常使用，但是计算机不好识别&& &&& &后缀表达式：abc*+dc/-:生活中不好使用，但计算机容易识别&& &&& &例： && &&& &总结：因此需要一种存储方法，能顺序的存储运算数，在需要时倒叙输出。--&堆栈有&& &&& &堆栈的特点：后入先出。&& &1.2堆栈的操作&& &操作集：长度为maxSize的堆栈S ==& stack,堆栈的元素elementType，那么如下的操作&& &&& &stack createStack(int maxSize);//生成空堆栈，其最大长度为maxSize&& &&& &int isFull(stack s,int maxSize);//判断栈s是否为空&& &&& &void push(stack& s,elementType item);//将元素压入堆栈&& &&& &int isEmpty(stack s);//判断堆栈是否为空&& &&& &elementType pop(stack s);//删除并返回栈顶元素&& &&& &&& &&& &1.2.1&& &&& &&& &用数组来表示堆栈的方法可以参照文件夹下面的同级目录的文件stackArray.c&& &&& &&& &同时还有使用一个数组来表示两个堆栈，twoStack.c&& &&& &&& &&& &1.2.2使用链表来模拟堆栈&& &&& &&& &因为链表有两头，但是堆栈的头指针我们会选择链表的头节点，因为便于删除操作，尾节点不方便进行删除操作&& &&& &&& &下面是模拟的示意图&& &&& &&& &&& &head(头指针，没有元素的) --& node1(top指针) --& node2(堆栈中的元素) --& node3 --& node4&& &&& &&& &代码可以见：stackLinkList.c&& &&& &1.2.3 利用堆栈进行表达式求值&& &&& &&& &我们平时所见到的表达式都是中缀表达式，但是如果想求表达式的值，先把中缀表达着中文后缀表达式，&& &&& &&& &在利用堆栈对后缀表达式进行求值&& &&& &&& &中缀表达式转后缀表达式的思路；&& &&& &&& &&& &首先看一个简单的：&& &&& &&& &&& &中缀表达式：2 + 9 / 3 - 5&& &后缀表达式：2 9 3 / + 5 -&& &&& &&& &&& &通过对比我们发现，中缀表达式和后缀表达式的数字顺序并没有发生改变，只是符号位置发生了改变&& &&& &&& &&& &所以，我们可以构思，使用一个栈来存在运算符，遇到数字就输出，遇到符号就压栈，如果读入的符号比栈顶的符号&& &&& &&& &&& &优先级高，就压栈，否则就弹栈并输出&& &&& &&& &&& &下面是中缀表达式：2 + 9 / 3 - 5压栈和弹栈的具体步骤&& &&& &&& &&& &输出&& &&& &堆栈内元素&& &&& &&& &&& &2&& &&& && &&& &&& &&& &&& &&& &&& &&& +&& &&& &&& &&& &9&& &&& && &&& &&& &&& &&& &&& &&& &&& /(优先级比+高，压栈)&& &&& &&& &&& &3&& &&& && &&& &&& &&& &&& &/ +&& &&& &&& -(首先弹出/,但是因为同级运行需要按照从左往右的运算，所以+也需要弹栈)&& &&& &&& &&& &5&& &&& &&& -&& &&& &&& &&& &-&& &&& && (元素全部读取完毕以后，-弹栈)&& &&& &&& &&& &所以中缀表达式：2 + 9 / 3 - 5的后缀表达式为 2 9 3 / + 5 -&& &&& &&& &&& &但是如果遇到带有()的表达式怎么办：遇到"("把"("压入栈中，此时栈中的"("运算级别最低，在按照上面的运算符的运算规则来&& &&& &&& &&& &进行压栈和弹栈。直到读取到")",才把"("弹栈，但是对"("和")"不进行输出&& &&& &&& &&& &举个例子：&& &&& &&& &&& &求下面中缀表达式：2 * (9+6/3-5)+4的后缀表达式&& &&& &&& &&& &输出&& &&& &&& &堆栈内元素(top-&bottom)&& &&& &&& &&& &2&& &&& &&& &&& &&& &&& &&& &&&&& *&& &&& &&& &&& &&& &&& &&& &&&&& ( *&& &&& &&& &&& &9&& &&& &&& &&&&& + ( * && &&& &&& &&& &6&& &&& &&& &&& &&& &&& &&& &&& &&& &&& &&&&& / + ( *&& &&& &&& &&& &3&& &&& &&& &&&& &&& &&& &&& &&& &&& &&& &&& &&&&& - ( *(首先弹出/,但是因为同级运行需要按照从左往右的运算，所以+也需要弹栈,并输出)&& &&& &&& &&&&&&&& / +&& &&& &&& &&& &5&& &&& &&& &&& &-&& &&& &&& &&&& *(遇到")",把栈里依次弹出，直到遇到第一个"(",但是对"("和")"不进行输出)&& &&& &&& &&& &*&& &&& &&& &&&& +(遇到+，先弹出*，然后输出)&& &&& &&& &&& &4&& &&& &&& &&&& +&& &&& &&& &&& &+&& &&& &&& &&&& NULL(没有元素可读，弹出堆栈中最后一个元素)&& &&& &&& &&& &&& &&& &&& &&& &所以中缀表达式：2 * (9+6/3-5)+4的后缀表达式为: 2 9 6 3 / + 5 - * 4 +代码实现
思路：中缀表达式先转后缀表达式在求值
只支持0-9之间的数字的+-*/以及(),支持括号里面嵌套括号，如3*(2*3-4*1+(3*5)/3)*3+2
不支持分开的括号3*(2*3-4*1+(3*5)/3)*3+2+(4/2)
如果有给出修改意见，感激不尽。写的比较匆忙，代码的复用性和注释的完整性可能不是很好
1 #include&stdio.h&
2 #include&stdlib.h&
3 #include&string.h&
4 #include&math.h&
5 #include&ctype.h&
6 #define MAXSIZE 100
9 #include&stdio.h&
10 #include&stdlib.h&
11 /*使用链表来模拟堆栈，*/
15 /*=======================================================定义double类型的堆栈链式存储并进行相关的压栈，弹栈等操作===============================================================*/
17 //定义double类型的堆栈的链式存储
18 typedef struct node3{
struct node3 *
21 }integerSta,*pIntegerS
23 //构造一个double类型的链式栈
24 pIntegerStack createIntegerEmptyStack(){
stack = (pIntegerStack)malloc(sizeof(integerSta));
if(stack){
stack-&next=NULL;
33 //判断double类型的链式栈是否为空
34 int isIntegerEmpty(pIntegerStack stack){
if(stack-&next==NULL){
return <span style="color: #;
return <span style="color: #;
43 void pushInteger(pIntegerStack stack,double element){
pIntegerStack node = (pIntegerStack)malloc(sizeof(integerSta));
node-&element=
node-&next=stack-&
stack-&next=
51 double popInteger(pIntegerStack stack){
pIntegerStack topH
if(isEmpty(stack)){
printf("the stack is empty,can not pop");
topHead = stack-&
stack-&next = topHead-&
element = topHead-&
free(topHead);
66 //取栈顶元素
67 double getIntegetStackTopElement(pIntegerStack stack){
return (stack-&next-&element);
71 //打印栈内元素
72 void toStringInteger(pIntegerStack stack){
pIntegerStack top = stack-&
printf("toString:");
while(top!=NULL){
printf("%f ",top-&element);
printf("\n");
85 /*================================================定义一个存储字符的线性表=========================================================================*/
89 //构造一个线性表存储后缀表达式
90 typedef struct node2{
char data[MAXSIZE];
93 }li,*pL
97 //初始化线性表
98 pList createEmptyList(){
<span style="color: #0
p = (pList)malloc(sizeof(li));
<span style="color: #1
<span style="color: #2
p-&length=-<span style="color: #;
<span style="color: #3
<span style="color: #4
<span style="color: #5 }
<span style="color: #6
<span style="color: #7 //向线性表中插入元素
<span style="color: #8 void insert(pList list,char c){
<span style="color: #9
<span style="color: #0
list-&data[++(list-&length)]=c;
<span style="color: #1
<span style="color: #2 }
<span style="color: #3
<span style="color: #4 //将线性表中的元素打印
<span style="color: #5 void toStringList(pList list){
<span style="color: #6
<span style="color: #7
for(i=<span style="color: #;i&=list-&i++){
<span style="color: #8
printf("%c ",list-&data[i]);
<span style="color: #9
<span style="color: #0
printf("\n");
<span style="color: #1
<span style="color: #2 }
<span style="color: #3
<span style="color: #4
<span style="color: #5
<span style="color: #6 /*==================================================定义一个字符栈并进行相关操作=================================================================*/
<span style="color: #7 //定义字符栈
<span style="color: #8 typedef struct node{
<span style="color: #9
<span style="color: #0
struct node *
<span style="color: #1 }sta,*pS
<span style="color: #2
<span style="color: #3 //创建一个空的字符链式栈
<span style="color: #4 pStack createEmptyStack(){
<span style="color: #5
<span style="color: #6
stack = (pStack)malloc(sizeof(sta));
<span style="color: #7
if(stack){
<span style="color: #8
stack-&next=NULL;
<span style="color: #9
<span style="color: #0
<span style="color: #1 }
<span style="color: #2
<span style="color: #3 //判断链式栈是否为空
<span style="color: #4 int isEmpty(pStack stack){
<span style="color: #5
if(stack-&next==NULL){
<span style="color: #6
return <span style="color: #;
<span style="color: #7
<span style="color: #8
return <span style="color: #;
<span style="color: #9
<span style="color: #0 }
<span style="color: #1
<span style="color: #2 //把元素压入栈
<span style="color: #3 void push(pStack stack,char element){
<span style="color: #4
pStack node = (pStack)malloc(sizeof(sta));
<span style="color: #5
node-&element=
<span style="color: #6
node-&next=stack-&
<span style="color: #7
stack-&next=
<span style="color: #8 }
<span style="color: #9
<span style="color: #0 //把元素弹栈
<span style="color: #1 char pop(pStack stack){
<span style="color: #2
<span style="color: #3
pStack topH
<span style="color: #4
if(isEmpty(stack)){
<span style="color: #5
printf("the stack is empty,can not pop");
<span style="color: #6
return NULL;
<span style="color: #7
<span style="color: #8
topHead = stack-&
<span style="color: #9
stack-&next = topHead-&
<span style="color: #0
element = topHead-&
<span style="color: #1
free(topHead);
<span style="color: #2
<span style="color: #3
<span style="color: #4 }
<span style="color: #5
<span style="color: #6 //获取栈顶元素
<span style="color: #7 char getTopElement(pStack stack){
<span style="color: #8
if(isEmpty(stack)){
<span style="color: #9
printf("the stack is empty,can not get top element");
<span style="color: #0
<span style="color: #1
<span style="color: #2
return (stack-&next-&element);
<span style="color: #3
<span style="color: #4 }
<span style="color: #5
<span style="color: #6
<span style="color: #7
<span style="color: #8 /*=============================================中缀表达式转后缀表达式=====================================================================*/
<span style="color: #9
<span style="color: #0
<span style="color: #1 //打印字符数组
<span style="color: #2 void charArrayToString(char *arr){
<span style="color: #3
<span style="color: #4
while(*p!='\0'){
<span style="color: #5
printf("%c ",*p);
<span style="color: #6
p = p+<span style="color: #;
<span style="color: #7
<span style="color: #8 }
<span style="color: #9
<span style="color: #0
<span style="color: #1
<span style="color: #2 /*
<span style="color: #3 判断字符c是否存在字符数组arr中
<span style="color: #4 存在，返回1
<span style="color: #5 不存在，返回0
<span style="color: #6 */
<span style="color: #7 int isCharArrContainChar(char arr[],char c){
<span style="color: #8
<span style="color: #9
while(*p!='\0'){
<span style="color: #0
if(*p==c){
<span style="color: #1
return <span style="color: #;
<span style="color: #2
<span style="color: #3
p = p+<span style="color: #;
<span style="color: #4
<span style="color: #5
return <span style="color: #;
<span style="color: #6 }
<span style="color: #7
<span style="color: #8
<span style="color: #9 /*给定一个运算符，判断他的优先级，返回数字越大，优先级越高，例如
<span style="color: #0
operatorPriorityArr是一个二维数组，下面是模拟的内容，优先级用户可以自定义，数组按元素优先级由低到高排列
<span style="color: #1
<span style="color: #2
<span style="color: #3
<span style="color: #4
<span style="color: #5
c:等待判断优先级的运算符
<span style="color: #6 */
<span style="color: #7 int getCharIndex(char c,char operatorPriorityArr[][MAXSIZE],int length){
<span style="color: #8
<span style="color: #9
for(i=<span style="color: #;i&i++){
<span style="color: #0
if(isCharArrContainChar(operatorPriorityArr[i],c)){
<span style="color: #1
<span style="color: #2
<span style="color: #3
<span style="color: #4
return -<span style="color: #;
<span style="color: #5 }
<span style="color: #6
<span style="color: #7
<span style="color: #8 /*
<span style="color: #9 判断字符栈的栈顶元素的优先级和读入字符的优先级
<span style="color: #0 参数：
<span style="color: #1
stackTopEle：栈顶元素
<span style="color: #2
readChar：读入的元素
<span style="color: #3
operatorPriorityArr：用户自定义的运算符优先级二维字符数组，数组按元素优先级由低到高排列
<span style="color: #4
length:二维数组的行数
<span style="color: #5
<span style="color: #6 比较规则：
<span style="color: #7
1.如果读入的字符为"(",那么"("的优先级最高，直接压栈
<span style="color: #8
2.如果栈顶元素为"(",其优先级最低，eadChar直接入栈
<span style="color: #9
3.如果读入的元素readChar优先级大于栈顶元素，则readChar入栈。例如eadChar为"*" topChar为"+",则"*"入栈
<span style="color: #0
4.如果读入的元素readChar优先级小于或者等于(因为运算需要按照从左往右的顺序)栈顶元素，则topChar弹栈并输出(记录)。
<span style="color: #1
再次判断readChar和当前栈顶元素的优先级，如果当readChar还是优先级小于或者等于当前栈顶元素，接着弹栈并输出(记录)。
<span style="color: #2
一直比较，直到readChar的优先级大于栈顶元素或者栈为空。
<span style="color: #3
5.如果readChar为")"，一直弹栈到到第一次遇到"(",并把"("也弹栈，对"("和")"不做输出，其运算符弹栈且输出(记录)
<span style="color: #4
<span style="color: #5
<span style="color: #6
<span style="color: #7
0：读入")" 直到把第一个"("弹栈栈为止
<span style="color: #8
2：弹出当前的栈顶元素，并继续比较
<span style="color: #9 */
<span style="color: #0 int compareOperatorChar(char stackTopEle,char readChar,char operatorPriorityArr[][MAXSIZE],int length){
<span style="color: #1
int index1,index2;
<span style="color: #2
if(stackTopEle=='('){
<span style="color: #3
return <span style="color: #;//栈为空，直接压栈
<span style="color: #4
}else if(readChar==')'){
<span style="color: #5
return <span style="color: #;//读入遇到")",直到把第一个"("弹栈栈为止
<span style="color: #6
<span style="color: #7
//获取两个运算符的优先级
<span style="color: #8
index1 = getCharIndex(stackTopEle,operatorPriorityArr,length);
<span style="color: #9
index2 = getCharIndex(readChar,operatorPriorityArr,length);
<span style="color: #0
if(index1&index2){//比较优先级
<span style="color: #1
return <span style="color: #;
<span style="color: #2
<span style="color: #3
return <span style="color: #;
<span style="color: #4
<span style="color: #5
<span style="color: #6 }
<span style="color: #7
<span style="color: #8
<span style="color: #9 /*
<span style="color: #0 根据优先级的返回结果进行对应的压栈和弹栈操作
<span style="color: #1 参数：
<span style="color: #2
stack:准备好的空字符栈
<span style="color: #3
readChar：读入的字符
<span style="color: #4
operatorPriorityArr:定义的优先级规则
<span style="color: #5
list：储存后缀表达式的字符线性表
<span style="color: #6
length：二维数组的行数
<span style="color: #7 */
<span style="color: #8 void comparePriority(pStack stack,char readChar,char operatorPriorityArr[][MAXSIZE],pList list,int length){
<span style="color: #9
if(isEmpty(stack)){
<span style="color: #0
push(stack,readChar);
<span style="color: #1
return <span style="color: #;
<span style="color: #2
<span style="color: #3
char topEle = getTopElement(stack);
<span style="color: #4
int result = compareOperatorChar(topEle,readChar,operatorPriorityArr,length);
<span style="color: #5
if(result==<span style="color: #){
<span style="color: #6
while(getTopElement(stack)!='('){
<span style="color: #7
insert(list,pop(stack));
<span style="color: #8
<span style="color: #9
pop(stack);
<span style="color: #0
<span style="color: #1
}else if(result==<span style="color: #){
<span style="color: #2
push(stack,readChar);
<span style="color: #3
<span style="color: #4
<span style="color: #5
insert(list,pop(stack));
<span style="color: #6
//递归再次比较
<span style="color: #7
comparePriority(stack,readChar,operatorPriorityArr,list,length);
<span style="color: #8
<span style="color: #9
<span style="color: #0 }
<span style="color: #1
<span style="color: #2
<span style="color: #3 /*
<span style="color: #4 根据中缀表达式或者后缀表达式，转换规则：
<span style="color: #5
1.对于数字，进行原样的输出或者记录
<span style="color: #6
2.对于运算符，根据优先级进行压栈弹栈操作，优先级比较规则参照上面
<span style="color: #7 参数：
<span style="color: #8
stack:准备好的空字符栈
<span style="color: #9
arr：中缀表达式的字符数组，支持空格隔开
<span style="color: #0
operatorPriorityArr:定义的优先级规则
<span style="color: #1
list：储存后缀表达式的字符线性表
<span style="color: #2
length：二维数组的行数
<span style="color: #3 */
<span style="color: #4 char* getBehindExpress(pStack stack,char *arr,char operatorPriorityArr[<span style="color: #][MAXSIZE],pList list,int length){
<span style="color: #5
<span style="color: #6
while(*p!='\0'){
<span style="color: #7
if(*p&='<span style="color: #' && *p&='<span style="color: #'){
<span style="color: #8
insert(list,*p);
<span style="color: #9
}else if(*p==' '){
<span style="color: #0
p = p+<span style="color: #;
<span style="color: #1
<span style="color: #2
}else if(getCharIndex(*p,operatorPriorityArr,length)!=-<span style="color: #){//判断运算符是否和法
<span style="color: #3
comparePriority(stack,*p,operatorPriorityArr,list,length);
<span style="color: #4
<span style="color: #5
printf("the operational character is illegal\n");
<span style="color: #6
return "error";
<span style="color: #7
<span style="color: #8
p = p+<span style="color: #;
<span style="color: #9
<span style="color: #0
//当数字读取完毕后，要把栈里面的运算符全部弹栈
<span style="color: #1
while(!isEmpty(stack)){
<span style="color: #2
insert(list,pop(stack));
<span style="color: #3
<span style="color: #4 }
<span style="color: #5
<span style="color: #6 //打印字符栈里面的元素
<span style="color: #7 void toString(pStack stack){
<span style="color: #8
pStack top = stack-&
<span style="color: #9
printf("toString:");
<span style="color: #0
while(top!=NULL){
<span style="color: #1
printf("%c ",top-&element);
<span style="color: #2
<span style="color: #3
<span style="color: #4
printf("\n");
<span style="color: #5 }
<span style="color: #6
<span style="color: #7
<span style="color: #8
<span style="color: #9
<span style="color: #0 /*==================================================计算后缀表达式的值==========================================================================*/
<span style="color: #1 /*计算规则如下：
<span style="color: #2 求后缀表达式的值
<span style="color: #3
6 2 / 3 - 4 2 * + =
<span style="color: #4
<span style="color: #5
后缀表达式的求解原理：遇到数值先记录(压栈)，遇到符号才计算(弹栈两个元素)。计算离符号最近的两个数
<span style="color: #6
1.6 2 / ==& 3 压栈
<span style="color: #7
2.3 3 - ==& 0 压栈
<span style="color: #8
3.0 4 2 * ==& 0 8
<span style="color: #9
4.0 8 + ==&8
<span style="color: #0
5.8 = ==& 8
<span style="color: #1 */
<span style="color: #2 double getValueByAfterExpress(pList list,pStack stack){
<span style="color: #3
<span style="color: #4
double temp,a1,a2;
<span style="color: #5
for(i=<span style="color: #;i&=list-&i++){
<span style="color: #6
//printf("test");
<span style="color: #7
char c = list-&data[i];
<span style="color: #8
if(c&='<span style="color: #' && c&='<span style="color: #'){
<span style="color: #9
store = c-'<span style="color: #';//字符转换为数字
<span style="color: #0
temp = store*<span style="color: #.0;//整形转换为double型
<span style="color: #1
//printf("double:%f\n",temp);
<span style="color: #2
pushInteger(stack,temp);//数字就压栈
<span style="color: #3
<span style="color: #4
//弹栈并根据运算符做运算
<span style="color: #5
double a1 = popInteger(stack);
<span style="color: #6
double a2 = popInteger(stack);
<span style="color: #7
if(list-&data[i]=='+'){
<span style="color: #8
temp = a1+a2;
<span style="color: #9
pushInteger(stack,temp);
<span style="color: #0
<span style="color: #1
<span style="color: #2
if(list-&data[i]=='-'){
<span style="color: #3
temp = a2-a1;
<span style="color: #4
pushInteger(stack,temp);
<span style="color: #5
<span style="color: #6
if(list-&data[i]=='*'){
<span style="color: #7
temp = a1*a2;
<span style="color: #8
pushInteger(stack,temp);
<span style="color: #9
<span style="color: #0
if(list-&data[i]=='/'){
<span style="color: #1
temp = a2/a1;
<span style="color: #2
pushInteger(stack,temp);
<span style="color: #3
<span style="color: #4
<span style="color: #5
<span style="color: #6
//toStringInteger(stack);
<span style="color: #7
<span style="color: #8
//最终的栈顶元素即为所求的值
<span style="color: #9
return getIntegetStackTopElement(stack);
<span style="color: #0 }
<span style="color: #1
<span style="color: #2
<span style="color: #3
<span style="color: #4 void main(){
<span style="color: #5
int n = <span style="color: #,i;
<span style="color: #6
pStack stack
= createEmptyStack();
<span style="color: #7
pStack numberStack
= createIntegerEmptyStack();
<span style="color: #8
pList list = createEmptyList();
<span style="color: #9
<span style="color: #0
char arr1[] = "<span style="color: # * ( 9 + 6 / 3 - 5 ) + 4";
<span style="color: #1
char arr2[] = "<span style="color: # + 9 / 3 - 5";
<span style="color: #2
char arr3[] = "<span style="color: #*(2*3-4*1+(3*5)/3)*3+2";
<span style="color: #3
char operatorPriorityArr[<span style="color: #][MAXSIZE]={"+-","*/","()"};
<span style="color: #4
//计算二维数组的行数
<span style="color: #5
int length=sizeof(operatorPriorityArr)/sizeof(operatorPriorityArr[<span style="color: #]);
<span style="color: #6
//char operatorArr[] = "+-*/()";
<span style="color: #7
getBehindExpress(stack,arr3,operatorPriorityArr,list,length);
<span style="color: #8
//toStringList(list);
<span style="color: #9
double value = getValueByAfterExpress(list,numberStack);
<span style="color: #0
printf("the express %s caculate result is %f",arr3,value);
<span style="color: #1
//double c = (double)('9.23');
<span style="color: #2
//printf("test:%f",c);
<span style="color: #3
//printf("%d",length);
<span style="color: #4 }
表达式求值
阅读(...) 评论()