人类最熟悉的一种表达式1+2,(1+2)*3,3+4 *2+4等等都是中缀表示法。对于人们来说,也是最直观的一种求值方式,先算括号里的, 因此,1920年,波兰科学家扬·武卡谢维奇(Jan ukasiewicz)发明了一种不需要括号的计算表达式的表示法将操作符号写在操作数之前,也就是前缀表达式,即波兰式(Polish Notation, PN)。 这里使用栗子: 算法伪代码(如果不清楚流程的话,务必要先看一下) 所以将上面的栗子放进去走一圈出来会怎样? in>>(1 + 2 * (4 – 3) + 6/2) 了解流程之后,我们来看个表:对于上面的栗子的转换 逆波兰表达式的计算就比较简单了。以上面结果中的队列为输入,同时再准备一个栈用于运算。具体流程如下: 对上面栗子进行流程化: ① 这是一个多项式计算器的代码,注释我就没放。 喜欢的话可以关注哦。什么是波兰表达式
然后算乘除,最后算加减,但是,计算机处理中缀表达式却并不方便,因为没有一种简单的数据结构可以方便从一个表达式中间抽出
一部分算完结果,再放进去,然后继续后面的计算(链表也许可以,但是,代价也是不菲)。
中缀表达式转逆波兰表达式
(1 + 2 * (4 - 3) + 6/2)
输入:中缀表达式串 输出:后缀表达式串 PROCESS BEGIN: 1.从左往右扫描中缀表达式串s,对于每一个操作数或操作符,执行以下操作; 2.IF (扫描到的s[i]是操作数DATA) 将s[i]添加到输出队列中; 3.IF (扫描到的s[i]是开括号'(') 将s[i]压栈; 4.WHILE (扫描到的s[i]是操作符OP) IF (栈为空 或 栈顶为'(' 或 扫描到的操作符优先级比栈顶操作符高) 将s[i]压栈; BREAK; ELSE 出栈至输出队列中 5.IF (扫描到的s[i]是闭括号')') 栈中运算符逐个出栈并输出,直到遇到开括号'('; 开括号'('出栈并丢弃; 6.返回第1.步 7.WHILE (扫描结束而栈中还有操作符) 操作符出栈并加到输出队列中 PROCESS END
out<<1 2 4 3 -*+ 6 2 / +
后缀表达式运算流程
②
③
放码过去
#ifndef _STACK_H_ #define _STACK_H_ #include <stdio.h> #include <stdlib.h> #define SIZE 10 typedef struct node { int data; struct node *next; }Node; typedef struct stack { Node *top; }Stack; void Init(Stack *s); int Empty(Stack *s); void Push(Stack *s, int data); void Pop(Stack *s); int GetTop(Stack *s); #endif
#include "stack.h" void Init(Stack *s) { if (NULL == s) return; s->top = NULL; } int Empty(Stack *s) { if (NULL == s) return 0; if (NULL == s->top) return 1; return 0; } void Push(Stack *s,int data) { if (NULL == s) return; Node *node = (Node *)malloc(sizeof(Node)/sizeof(char)); if (NULL == node) return; node->data = data; node->next = s->top; s->top = node; } void Pop(Stack *s) { if (NULL == s) return; if (Empty(s) == 1) return; Node *tmp = s->top; s->top = tmp->next; free(tmp); } int GetTop(Stack *s) { if (NULL == s) return; if (Empty(s) == 1) { printf ("无栈顶元素n"); exit(-1); } return s->top->data; }
#include <stdio.h> #include "stack.h" #include <string.h> int Ope_judge(Stack *s_ope,int ope) { if(Empty(s_ope)) return 1; int top = GetTop(s_ope); switch(top) { case '+': case '-': if(ope == '*' || ope == '/' || ope == '(') return 1; break; case '*': case '/': if( ope == '(') return 1; break; case '(': if(ope == ')') { Pop(s_ope); } return 1; default : break; } return 0; } void Calc(Stack *s_ope,Stack *s_num) { int num1 = GetTop(s_num); Pop(s_num); int num2 = GetTop(s_num); Pop(s_num); int ope = GetTop(s_ope); Pop(s_ope); int res; switch(ope) { case '+': res = num2 + num1; break; case '-': res = num2 - num1; break; case '*': res = num2 * num1; break; case '/': res = num2 / num1; break; default: break; } Push(s_num,res); } void Ope_deal(Stack *s_ope,Stack *s_num,int ope) { if(Ope_judge(s_ope,ope) == 1) { Push(s_ope,ope); } else { while(Ope_judge(s_ope,ope) == 0) { Calc(s_ope,s_num); } if(ope != ')') Push(s_ope,ope); } } int main() { char buf[100]; fgets(buf,100,stdin); buf[strlen(buf)-1] = ' '; Stack s_num; Stack s_ope; Init (&s_num); Init (&s_ope); char *p = buf; while(*p) { if(*p >= '0' && *p <= '9') { int num = 0; while(*p >= '0' && *p <= '9') { num = num *10 + *p - '0'; p++; } Push(&s_num , num); continue; } Ope_deal(&s_ope,&s_num,*p); p++; } while(!Empty(&s_ope)) { Calc(&s_ope,&s_num); } int res = GetTop(&s_num); printf ("计算结果为:%dn", res); return 0; }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算