C语言之逆波兰表达式完整代码(附算法)

今天用栈编写了一个后缀表达式(逆波兰式求值)求值的程序。

在书中栈的基本类型是int型，我这里用char类型实现。

所以操作数是有限制的。

代码如下：#include<iostream>#include<string>using namespace std;const int baseSize=30,reSize=10;typedef char elem;typedef struct{elem *base;int top;int stacksize;}SeqStack;void InitStack(SeqStack & S,int maxsize){if(maxsize<=0)maxsize=baseSize;S.base=new char[maxsize];if(!S.base){cout<<"memory allocation failure\n";exit(1);}S.stacksize=maxsize;S.top=0;}bool stacktop(SeqStack & S,char &e){if(!S.top) return false;e=S.base[S.top-1];return true;}bool push(SeqStack &S ,char e)if(S.top>=S.stacksize){cout<<"stack is full\n";return false;}S.base[S.top++]=e;return true;}bool pop(SeqStack & S,char& e) {if(!S.base) return fal se;e=S.base[--S.top];return true;}void get_PolishList(char *a){char m_strPolish[50];gets(m_strPolish);strcpy(a,m_strPolish);}int getvalue(char op,char a,char b) {switch(op){case'+':return (a-'0')+(b-'0');case'-':return (a-'0')-(b-'0');case'*':return (a-'0')*(b-'0');case'/':return (a-'0')/(b-'0');}}int main(void){SeqStack Polish;InitStack(Polish,40);char m_strPolish[60];get_PolishList(m_strPolish);for(int i=0;i<strlen(m_strPolish);i++){if(m_strPolish[i]<'9'&&m_strPolish[i]>'0')push(Polish,m_strPolish[i]);else{char var1,var2;pop(Polish,var1);pop(Polish,var2);push(Polish,getvalue(m_strPolish[i],var2,var1)+'0');}}int result=0;char value;pop(Polish,value);cout<<"Result: "<<value-'0'<<endl;// cout<<m_strPolish<<endl;return 250;}测试数据是：3*5+(6-8/4)*7 转换成后缀表达式35*684/-7*+；结果如图：。

中国计量学院《编译原理设计》课程论文题目：中缀表达式的逆波兰表示学生姓名：学号：学生专业：班级：二级学院：一、摘要编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。

由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。

本课程设计正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。

我们这次课程设计的主要任务是编程实现对输入合法的中缀表达式进行词法分析、语法分析，构造相应的逆波兰式，计算后缀表达式的值输出结果。

逆波兰式也叫后缀表达式，即将运算符写在操作数之后。

通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。

同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。

关键字：逆波兰式；语法分析；中缀表达式二、实验综述在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。

对中缀表达式的计值，并非按运算符出现的自然顺序来执行其中的各个运算，而是根据算符间的优先关系来确定运算的次序，此外，还应顾及括号规则。

因此，要从中缀表达式直接产生目标代码一般比较麻烦。

相对的，逆波兰式在计算机看来却是比较简单易懂的结构。

因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

三、实验意义对于实现逆波兰式算法，难度并不大，但为什么要将看似简单的中缀表达式转换为逆波兰式，原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中缀表达式是非常复杂的结构。

相对的，逆波兰式在计算机看来却是比较简单易懂的结构。

因为计算机普遍采用的内存结构是栈式结构，它执行四、系统分析词法分析基本原理：词法分析程序完成的是编译第一阶段的工作。

逆波兰式（后缀表达式）的计算输⼊：后缀表达式（可带浮点数）输出：double型的计算结果代码：#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define ElemType double#define Stack_Init_Size 100#define Increase_Size 10#define MaxBuffer 10typedef struct sqStack{ElemType *top;ElemType *base;int initSize;}sqStack;typedef struct sqStack *LinkStack;//初始化void InitStack( sqStack *s ){s->base = (LinkStack)malloc(Stack_Init_Size * sizeof(ElemType));if(!s->base){printf("存储空间分配失败······\n");return;}s->top = s->base;s->initSize = Stack_Init_Size;}//进栈void Push(sqStack *s,ElemType e){if(s->top - s->base >= s->initSize - 1){s->base = (LinkStack)realloc(s->base,(s->initSize + Increase_Size) * sizeof(ElemType));//第⼀个s->base是增加后的存储空间块的地址，第⼆个是增加空间之前的存储空间块地址，后⾯是增加过的存储空间块的⼤⼩ if(!s->base){printf("增加存储空间失败······\n");return;}s->initSize = Increase_Size + Stack_Init_Size;}*(s->top) = e;(s->top)++;}//出栈void Pop(sqStack *s,ElemType *e){if(s->top == s->base){printf("栈已空，⽆法进⾏出栈操作······\n");return;}s->top--;*e = *s->top;}//求栈的长度int StackLen(sqStack s){return (s.top - s.base);}//逆波兰计算器：输⼊逆波兰式（后缀表达式）输出结果int main(){int i = 0,j,len;double m,n,t;char c;struct sqStack s;char str[MaxBuffer];InitStack(&s);printf("请输⼊您要计算的后缀表达式，按Enter键结束（两个不同的字符之间⽤空格隔开）：\n");scanf("%c",&c);while(c != '\n'){while( (c >= '0'&&c <= '9') || c == '.'){str[i] = c;i++;// str[i] = '\0';if(i >= 10){printf("\n输⼊的数字过⼤导致出错\n"); return -1;}scanf("%c",&c);if( c == ' '){t = atof(str);// printf("\nt is %f\n",t);Push(&s,t);i = 0;for(j = 0;j < MaxBuffer;j++){str[j] = '\0';}break;}}switch( c ){case '+':Pop(&s,&m);Pop(&s,&n);Push(&s,n+m);break;case '-':Pop(&s,&m);Pop(&s,&n);Push(&s,n-m);break;case '*':Pop(&s,&m);Pop(&s,&n);Push(&s,n*m);break;case '/':Pop(&s,&m);Pop(&s,&n);if( m == 0){printf("\n除数为0，出错\n");return -1;}else{Push(&s,n/m);break;}}scanf("%c",&c);}Pop(&s,&t);printf("\n最终的计算结果为：%f \n",t);return 0;}。

c#实现逆波兰式运⽤⼤众例⼦：所谓的逆波兰表⽰法（Reverse Polish notation，RPN，或逆波兰记法），是⼀种数学表达式⽅式，在逆波兰记法中，所有操作符置于操作数的后⾯，因此也被称为后缀表⽰法。

逆波兰记法不需要括号来标识操作符的优先级。

（摘⾃维基）我们平时长写的数学公式被称为中缀表达式，即:(a+b)*c,⽤逆波兰式为ab+c*,再如：(a+b)*c-(a+b)/e,逆波兰式为ab+c*ab+e/-，⾸先理解下转化成逆波兰式的⼏个步骤：算法实现(选⾃百度)：⾸先需要分配2个栈，⼀个作为临时存储运算符的栈S1（含⼀个结束符号），⼀个作为输⼊逆波兰式的栈S2（空栈），S1栈可先放⼊优先级最低的运算符#，注意，中缀式应以此最低优先级的运算符结束。

可指定其他字符，不⼀定⾮#不可。

从中缀式的左端开始取字符，逐序进⾏如下步骤：（1）若取出的字符是，则分析出完整的运算数，该操作数直接送⼊S2栈（2）若取出的字符是，则将该运算符与S1栈栈顶元素⽐较，如果该⼤于S1栈栈顶运算符优先级，则将该运算符进S1栈，否则，将S1栈的栈顶运算符弹出，送⼊S2栈中，直⾄S1栈栈顶运算符低于（不包括等于）该运算符优先级，最后将该运算符送⼊S1栈。

（3）若取出的字符是“（”，则直接送⼊S1栈顶。

（4）若取出的字符是“）”，则将距离S1栈栈顶最近的“（”之间的运算符，逐个，依次送⼊S2栈，此时抛弃“（”。

（5）重复上⾯的1~4步，直⾄处理完所有的输⼊字符（6）若取出的字符是“#”，则将S1栈内所有运算符（不包括“#”），逐个出栈，依次送⼊S2栈。

最后出来的S2需要逆序处理下，便是逆波兰表达式了。

看着定义，然后粗略了实现了下⾯的代码：主⽅法：static void Main(string[] args){while (true){Console.WriteLine("输⼊计算公式:");//输⼊公式string formula = Console.ReadLine();//定义临时计算符栈Stack<string> opStack = new Stack<string>();opStack.Push("#");Stack<string> numStack = new Stack<string>();for (int i = 0; i < formula.Length;){int opNum = GetOperationLevel(formula[i].ToString());if (opNum == 0){int index = GetCompleteValue(formula.Substring(i, formula.Length - i));numStack.Push(formula.Substring(i, index));i = (i + index);}//为操作数，获取完整else{if (formula[i] == '('){opStack.Push(formula[i].ToString());}else if (formula[i] == ')'){MoveOperator(opStack, numStack);}else{if (opStack.Peek() == "("){opStack.Push(formula[i].ToString());}else{JudgeOperator(opStack, numStack, formula[i].ToString());}}i++;}}if (opStack.Count != 0){while (opStack.Count != 0 && opStack.Peek() != "#"){numStack.Push(opStack.Pop());}}StringBuilder strBuild = new StringBuilder();foreach (string s in numStack){strBuild.Insert(0,s);}Console.WriteLine(strBuild.ToString());}}获取运算符等级：///<summary>///获取运算符等级///</summary>///<param name="c">当前字符</param>///<returns></returns>private static int GetOperationLevel(string c){switch (c){case"+": return1;case"-": return1;case"*": return2;case"/": return2;case"#": return -1;case"(": return -1;case")": return -1;default: return0;}}获取完整操作数///<summary>///获取完整数值///</summary>///<param name="formula">公式</param>///<returns></returns>private static int GetCompleteValue(string formula){int index = formula.Length;for (int i = 0; i < formula.Length; i++){int num = GetOperationLevel(formula[i].ToString());if (num != 0){index = i;break;}}return index;}移动运算符：///<summary>///移动运算符///</summary>///<param name="opStack"></param>///<param name="numStack"></param>private static void MoveOperator(Stack<string> opStack, Stack<string> numStack) {string s = opStack.Pop();if (s == "("){return;}else{numStack.Push(s);MoveOperator(opStack, numStack);return;}}判断运算符:///<summary>///判断运算符///</summary>///<param name="opStack"></param>///<param name="numStack"></param>///<param name="x"></param>private static void JudgeOperator(Stack<string> opStack, Stack<string> numStack, string x){int xNum = GetOperationLevel(x);int opNum = GetOperationLevel(opStack.Peek());if (xNum > opNum || numStack.Peek() == "("){opStack.Push(x);return;}else{string opStr = opStack.Pop();numStack.Push(opStr);JudgeOperator(opStack, numStack, x);return;}}代码运⾏效果：接下来就是计算公式的值，思路是新建⼀个栈R⽤来放结果，依次取出表达式的栈F，1.如果取出的值为操作数，则放⼊栈R，2.如果取出的值为运算符，则取出栈R顶的两个，进⾏运算，运算结果在存放⼊栈R 最后R顶的元素，即为计算的值下⾯为代码，⽬前只做了+,-,*,///numStack为逆波兰表达式Stack<string> rpnFormula = new Stack<string>();foreach (string s in numStack){rpnFormula.Push(s);}Console.WriteLine(CalcRPNFormula(rpnFormula));=private static string CalcRPNFormula(Stack<string> rpnFormula){Stack<string> resultStack = new Stack<string>();foreach (string s in rpnFormula){int num = GetOperationLevel(s);if (num == 0){resultStack.Push(s);}else{CalcResult(resultStack,s);}}return resultStack.Pop();}private static void CalcResult(Stack<string> resultStack, string operatorStr){if (resultStack.Count >= 2){double num2 = Convert.ToDouble(resultStack.Pop());double num1 = Convert.ToDouble(resultStack.Pop());if (operatorStr == "+"){resultStack.Push(Convert.ToString(num1 + num2));}else if (operatorStr == "-"){resultStack.Push(Convert.ToString(num1 - num2));}else if (operatorStr == "*"){resultStack.Push(Convert.ToString(num1 * num2));}else if (operatorStr == "/"){resultStack.Push(Convert.ToString(num1 / num2));}}}因为适应⾃⼰的项⽬，需要做到⽀持“”^”,"arctan", "sqrt", "sin", "cos", "tan", "arcsin", "arccos"的计算⽅式，在查看上⾯⽣成的逆波兰式的时候，发现^会后置，其他的都是前置，然后就投机取巧了以下，遇到^取前两位，遇到其他特殊符号，则取后⼀位，所以增加了以下内容，测试了下例⼦:2^3+sqrt(9)+sin(45)+1 通过之前的代码转换为后缀表达式为23^sqrt9+sin45+1+(正确应为23^9sqrt+45sin+1+),然后根据上述的进⾏计算，加了这⼏个特许计算后，可能与原来的后缀表达式有点背道⽽驰，没有对特殊字符进⾏后置处理，但⽬前为了先实现计算，所以投机取巧了下，后期会进⾏修改///<summary>///特殊字符///</summary>private static List<string> m_SpecialOp = new List<string>() { "arctan", "sqrt", "sin", "cos", "tan", "arcsin", "arccos" };///<summary>///获取运算符等级///</summary>///<param name="c">当前字符</param>///<returns></returns>private static int GetOperationLevel(string c){//sin(cos(tan(arcsin(arccos(arctan(switch (c){case"+": return1;case"-": return1;case"*": return2;case"/": return2;case"^": return2;case"arctan": return10;case"sqrt": return10;case"sin": return10;case"cos": return10;case"tan": return10;case"arcsin": return10;case"arccos": return10;case"#": return -1;case"(": return -1;case")": return -1;default: return0;}}///<summary>///计算逆波兰式///</summary>///<param name="rpnFormula"></param>///<returns></returns>private static string CalcRPNFormula(Stack<string> rpnFormula){Stack<string> resultStack = new Stack<string>();while (rpnFormula.Count > 0){string rpnStr = rpnFormula.Pop();int num = GetOperationLevel(rpnStr);if (num == 0){resultStack.Push(rpnStr);}else if (num == 10){SpecialCalc(resultStack, rpnStr, rpnFormula.Pop());}else{CalcResult(resultStack, rpnStr);}}return resultStack.Pop();}///<summary>///特殊计算///</summary>///<param name="resultStack"></param>///<param name="operatorStr"></param>///<param name="calcValue"></param>private static void SpecialCalc(Stack<string> resultStack, string operatorStr, string calcValue) {if (m_SpecialOp.Contains(operatorStr)){double num = Convert.ToDouble(calcValue);if (operatorStr == "sqrt"){resultStack.Push(Math.Sqrt(num).ToString("#0.000"));}else if (operatorStr == "sin"){resultStack.Push(Math.Sin(num).ToString("#0.000"));}else if (operatorStr == "cos"){resultStack.Push(Math.Cos(num).ToString("#0.000"));}else if (operatorStr == "tan"){resultStack.Push(Math.Tan(num).ToString("#0.000"));}else if (operatorStr == "arcsin"){resultStack.Push(Math.Asin(num).ToString("#0.000"));}else if (operatorStr == "arccos"){resultStack.Push(Math.Acos(num).ToString("#0.000"));}else if (operatorStr == "arctan"){resultStack.Push(Math.Atan(num).ToString("#0.000"));}}}///<summary>///计算结果///</summary>///<param name="resultStack"></param>///<param name="operatorStr"></param>private static void CalcResult(Stack<string> resultStack, string operatorStr){if (resultStack.Count >= 2){double num2 = Convert.ToDouble(resultStack.Pop());double num1 = Convert.ToDouble(resultStack.Pop());if (operatorStr == "+"){resultStack.Push(Convert.ToString(num1 + num2));}else if (operatorStr == "-"){resultStack.Push(Convert.ToString(num1 - num2));}else if (operatorStr == "*"){resultStack.Push(Convert.ToString(num1 * num2));}else if (operatorStr == "/"){resultStack.Push(Convert.ToString(num1 / num2));}else if (operatorStr == "^"){resultStack.Push(Math.Pow(num1, num2).ToString());}}}。

逆波兰表达式求值一、需求分析1、从键盘中输入一个后缀表达式，该表示包括加减乘除等操作符，以及正整数作为操作数等。

2、用堆栈来实现3、测试数据输入：2 3 * 1 – #输出：2 3 * 1 -- =5二、概要设计抽象数据类型需要一个浮点数栈来存储还没有计算的浮点数或者运算的结果。

ADT Stack数据成员：int size; int top; //分别用于存储栈大小、栈顶位置float *listArray;//存储浮点型数字的数组成员函数：bool push(float it);bool pop(float& it);bool isEmpty(); //判断栈为空bool isOne();//判断栈是否只有一个元素算法的基本思想1. 逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+str[i]-48将数据由字符类型转换为浮点型数据；2. 如果字符是‘.’，则将‘.’转化为小数点，并将‘.’后的数据转化为小数部分；3. 遇到空格前是数据的，将x押入栈；4. 如果该字符是’+’，’-’，’*’或’/’，判断栈里的元素是否少于两个个，如果少于两个，报错；如果大于等于两个，就弹出两个数据，并进行相应的计算；程序的流程输入字符串，程序对字符串依次扫描。

扫描一位，处理一位。

扫描完成后，判断栈里是不是只有一个数据，若是，得到正确结果；若不是，则表达式出错。

三、详细设计物理数据类型用浮点数类型的栈存储运算中要用的数据，需要入栈、出栈，故设计如下的浮点类型的栈：class Stack{private:int size;int top;float *listArray;public:Stack(int sz=20);~Stack();bool push(float it);//入栈bool pop(float& it);//出栈bool isEmpty();//判断栈是否为空bool isOne(); //判断栈里是否只有且仅有一个元素};成员函数的函数体Stack::Stack(int sz) //栈构造函数{size=sz;top=0;listArray=new float[size]; }bool Stack::push(float it) {if(top==size)return false;listArray[top++]=it;return true;}bool Stack::pop(float& it) {if(top==0)return false;it=listArray[--top];return true;}bool Stack::isEmpty() //判断站是否为空{if(top==0)return true;return false;}bool Stack::isOne(){if(top==1)return true;return false;}Stack::~Stack(){delete listArray;}算法的具体步骤用switch语句实现1. 逐一扫描字符串，用ascii码进行判断，如果该字符是数字，则利用x=x*10+str[i]-48将数据由字符类型转换为浮点型数据；2. 如果字符是‘.’，则将‘.’转化为小数点，并将‘.’后的数据转化为小数部分；3. 遇到空格前是数据的，将x押入栈；4. 如果该字符是’+’，’-’，’*’或’/’，判断栈里的元素是否少于两个个，如果少于两个，报错；如果大于等于两个，就弹出两个数据，并进行相应的计算；算法的时空分析因为入栈、出栈的时间复杂度均为Θ(1)，所以时间的复杂度主要取决于字符串的长度，空间也同样取决于字符串长度。

C语⾔实现逆波兰式实例复制代码代码如下:#include<stdio.h>#include<string.h>typedef struct{char s[20][20];int top;}SQ;void copystr(char *a,char *b){int i=0;do{b[i]=a[i];i++;}while(a[i]!='\0');b[i]='\0';}void voidSQ(SQ *s){s->top=-1;}int ifempty(SQ *s){return(s->top==-1);}void push(SQ *S,char *c){if(S->top==19)printf("over flow\n");else{S->top++;copystr(c,S->s[S->top]);}}char *pop(SQ *S){if(ifempty(S)){printf("over flow!\n");return(NULL);}elsereturn(S->s[S->top--]);}int judge(char *c){if(c[1]=='\0')switch(c[0]){case '+':return(3);case '-':return(3);case '*':return(2);case '/':return(2);default:return(1);}elsereturn(1);}void write(char *a,char *b,char *c){strcat(a,c);strcat(a,b);}int seek(char *c,int start){int signal=1;for(start=start++;c[start]!='\0'&&signal!=0;start++) {if(c[start]==')')signal--;else if(c[start]=='(')signal++;}if(signal==0)return(start-1);else{printf("输⼊⽆效式⼦\n");return(-1);}}void FB(SQ *A,SQ *B){for(;!ifempty(A);){push(B,A->s[A->top]);pop(A);}}char *rewrite(char *A){SQ front;SQ back;int i,j,k,flag=0;char *result;char mid[20];voidSQ(&front);voidSQ(&back);for(i=0;A[i]!='\0';){if(A[i]=='('){j=seek(A,i);for(k=i+1;k<j;k++){mid[k-i-1]=A[k];}mid[j-i-1]='\0';copystr(rewrite(mid),mid);push(&back,mid);i=j+1;}else if(A[i]!='(')mid[0]=A[i];mid[1]='\0';push(&back,mid);i++;}}FB(&back,&front);for(;front.top>=2;){flag=0;for(i=0;i<=front.top;i++){if(judge(front.s[i])==2){flag=1;break;}}if(flag==1){for(;front.top>=2;){if(judge(front.s[front.top])==1&&judge(front.s[front.top-1])==2&&judge(front.s[front.top-2])==1) {write(front.s[front.top],front.s[front.top-1],front.s[front.top-2]);push(&back,front.s[front.top]);pop(&front);pop(&front);pop(&front);}else{push(&back,front.s[front.top]);pop(&front);}}FB(&front,&back);FB(&back,&front);}else{for(;front.top>=2;){if(judge(front.s[front.top])==1&&judge(front.s[front.top-1])==3&&judge(front.s[front.top-2])==1) {write(front.s[front.top],front.s[front.top-1],front.s[front.top-2]);push(&back,front.s[front.top]);pop(&front);pop(&front);pop(&front);}else{push(&back,front.s[front.top]);pop(&front);}}FB(&front,&back);FB(&back,&front);}result=front.s[front.top];return(result);}typedef struct{char c[20];int top;}sq; int execute(char a,char b,char c) {switch(a){case('+'):return((c-48)+(b-48)); case('-'):return((c-48)-(b-48));case('*'):return((c-48)*(b-48));case('/'):return((c-48)/(b-48));}}void voidsq(sq *s){s->top=-1;}int ifsqempty(sq *s){return(s->top==-1);}void pushsq(sq *s,char x){if(s->top==19)printf("over flow!\n");else{s->top=s->top+1;s->c[s->top]=x;}}void popsq(sq *s){if(ifsqempty(s))printf("over flow!\n");elses->top--;}int just(char c){switch(c){case ('+'):return(0);case ('-'):return(0);case ('*'):return(0);case ('/'):return(0);default:return(1);}}void restread(sq *a,sq *b){for(;!ifsqempty(a);){pushsq(b,a->c[a->top]);popsq(a);}}int calculate(char *c){sq rest,read;int i,re;voidsq(&rest);voidsq(&read);for(i=0;c[i]!='\0';i++)pushsq(&read,c[i]);for(;read.top>=2;){for(;read.top>=2;){if(just(read.c[read.top])==0&&just(read.c[read.top-1])==1&&just(read.c[read.top-2]) ==1) {re=execute(read.c[read.top],read.c[read.top-1],read.c[read.top-2]);pushsq(&rest,re+48);popsq(&read);popsq(&read);popsq(&read);}else{pushsq(&rest,read.c[read.top]);popsq(&read);}}restread(&read,&rest);restread(&rest,&read);}return(read.c[0]-48);}void main(){char re[20];char a[20];printf("请输⼊算式：\n");scanf("%s",a);copystr(rewrite(a),re);printf("逆波兰式：\n%s\n",re);printf("求值结果：\n%d\n",calculate(re));}。

源码：#include<stdio.h>#include<string.h>int main(){bool jud(char stack[], int n);char str[100];char exp[100];char stack[100];char ch;int flag=1;unsigned int zs;while(true){int i=0,j=0,t=0,top=0,k=0,l=0;printf("---语法制导把表达式翻译成逆波兰式---\n"); printf("请输入表达式:");scanf("%s",str);zs=strlen(str);str[zs]='#';ch=str[i];while(ch!='#'){if((ch>='a'&&ch<'z')||(ch>='0'&&ch<='9')){exp[t]=ch;t++;}else if(ch=='('){top++;stack[top]=ch;k++;}else if(ch=='^'){exp[t]=ch;t++;}else if(ch==')'){if(top!=0){if(jud(stack,top)){while(stack[top]!='('){exp[t]=stack[top];top--;t++;}top--;l++;}else{printf("括号不匹配!\n");flag=0;break;}}else{printf("括号不匹配!\n");flag=0;break;}}else if(ch=='+'||ch=='-'){while(top!=0&&stack[top]!='('){exp[t]=stack[top];top--;t++;}top++;stack[top]=ch;}else if(ch=='*'||ch=='/'){while(stack[top]=='*'||stack[top]=='/'){exp[t]=stack[top];top--;t++;}top++;stack[top]=ch;}else{printf("第%d个字母开始出错!\n",i+1);flag=0;break;}i++;ch=str[i];}if(k!=l){printf("括号不匹配!\n");flag=0;}else if (str[zs-1]=='+'||str[zs-1]=='-'||str[zs-1]=='*'||str[zs-1]=='/'){printf("该式不是中缀表达式!\n");flag=0;}if(flag!=0){while(top!=0){exp[t]=stack[top];t++;top--;}printf("逆波兰式输出:");for(j=0;j<t;j++)printf("%c",exp[j]);printf("\n");}}return 0;}bool jud(char stack[] ,int n){int i;for( i = 0;i<n;i++){if(stack[i]=='('){return true;break;}}}测试结果：。

逆波兰表达式逆波兰表达式题⼲正常的表达式称为中缀表达式，运算符在中间，主要是给⼈阅读的，机器求解并不⽅便。

例如：3 + 5 * (2 + 6) - 1⽽且，常常需要⽤括号来改变运算次序。

相反，如果使⽤逆波兰表达式（前缀表达式）表⽰，上⾯的算式则表⽰为：- + 3 * 5 + 2 6 1不再需要括号，机器可以⽤递归的⽅法很⽅便地求解。

为了简便，我们假设：只有 + - * 三种运算符每个运算数都是⼀个⼩于10的⾮负整数下⾯的程序对⼀个逆波兰表⽰串进⾏求值。

其返回值为⼀个结构：其中第⼀元素表⽰求值结果，第⼆个元素表⽰它已解析的字符数。

public static int[] evaluate(String x){if(x.length() == 0) return new int[]{0,0};char c = x.charAt(0);if (c >= '0' && c <= '9')return new int[]{c - '0', 1};int[] v1 = evaluate(x.substring(1));int[] v2 = __________________________________;//填空位置int v = Integer.MAX_VALUE;if (c == '+') v = v1[0] + v2[0];if (c == '*') v = v1[0] * v2[0];if (c == '-') v = v1[0] - v2[0];return new int[]{v, 1 + v1[1] + v2[1]};}代码public class _06逆波兰表达式 {// int[]数组中// 其中第⼀元素表⽰求值结果，第⼆个元素表⽰它已解析的字符数。

public static int[] evaluate(String x){if(x.length() == 0) return new int[]{0,0}; //char c = x.charAt(0); //取到⾸字符if (c >= '0' && c <= '9') //如果是数字return new int[]{c - '0', 1};// 如果是下⾯的情况，说明是字符，虽然此处没有else但是所表达的意思就是上⾯if之外的情况，因为上⾯的if没有执⾏的话才能够运⾏到下⼀⾏代码int[] v1 = evaluate(x.substring(1));//这⾥是除去第⼀个字符不要的其他部分，第⼀个字符是运算符int[] v2 = evaluate(x.substring(1+v1[1]));//填空位置，猜测是截取上⼀次没有处理到的部分// v1[1]处理v1消耗的字符数量//int v = Integer.MAX_VALUE;if (c == '+') v = v1[0] + v2[0];if (c == '*') v = v1[0] * v2[0];if (c == '-') v = v1[0] - v2[0];return new int[]{v, 1 + v1[1] + v2[1]};}public static void main(String[] args) {// TODO Auto-generated method stubSystem.out.println(evaluate("-+3*5+261")[0]);}}总结1.观察代码，也是从第⼀个字符开始：如果是数字，那么直接返回；如果不是，说明遇到了⼀个操作符，那么v1从这个操作符的后⼀位字符开始递归，直到遇到数字返回；然后v2再进⾏⼀些操作；最后把v1和v2对应的值对于回溯时最近的那个操作符进⾏运算。

#include<stdio.h>#include<ctype.h>#include<stack>#include<iostream>using namespace std;#define max 100int precedence(char op){//用于返回算符的优先级switch(op){case '+':case '-':return 1;case '*':case '/':return 2;case '(':case '#':default:return 0;}}void Change(char *s1,char *s2){//讲中缀表达式变成后缀表达式stack<char> R;R.push('#');int i,j;i=0;j=0;char ch=s1[i];while(ch!='#'){if(ch==' '){//遇到空格，则掉过继续ch=s1[++i];continue;}if(ch=='('){//左括号入栈R.push(ch);ch=s1[++i];continue;}if(ch==')'){while(R.top()!='('){s2[j++]=R.top();R.pop();}R.pop();//不要栈中的左括号ch=s1[++i];continue;}if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){char w=R.top();while(precedence(w)>precedence(ch))//比较栈顶和当前运算符的优先级，不能取等于号{s2[j++]=w;R.pop();w=R.top();}R.push(ch);ch=s1[++i];continue;}else//数子或者是小数点{while(isdigit(ch)||ch=='.'){s2[j++]=ch;ch=s1[++i];}s2[j++]=' ';continue;}}ch=R.top();while(ch!='#'){if(ch=='('){printf("expression error!");exit(1);}else{s2[j++]=ch;R.pop();ch=R.top();}}s2[j++]='#';s2[j++]='\0';}int Operate(int a,char theta,int b){switch(theta){case '+':return a+b;break;case '-':return a-b;break;case '*':return a*b;break;case '/':return a/b;break;default:return 0;}}int caculate(char *s){//采用后缀表达是计算表达式的值stack<int> R;R.push('#');char ch;int i=0;ch=s[i];int tmp=0;int sum=0;int a=0,b=0;while(ch!='#'){if(isdigit(ch)){while(isdigit(ch)){tmp=tmp*10+ch-'0';ch=s[++i];}R.push(tmp);tmp=0;}if(ch==' '){ch=s[++i];continue;}if(ch=='*'||ch=='/'||ch=='+'||ch=='-'){b=R.top();R.pop();a=R.top();R.pop();sum=Operate(a,ch,b);R.push(sum);ch=s[++i];}}return R.top();}int main(){char s1[max];char s2[max];gets(s1);//可以读取空格，而scanf不能读取有空格的字符串，既是读到空格，后面的字符便不再读入Change(s1,s2);printf("表达式的逆波兰表示为:%s\n",s2);printf("\n表达式的值是:%d",caculate(s2));return 0;}。