网站开发与电子商务,网站建设 新闻,公司网站如何更改内容,wordpress minfy一、基本概念
中缀表达式#xff1a;运算符都在运算数之间的表达式#xff0c;也就是我们日常见到的表达式#xff0c;包含括号。例如#xff1a;(12)*5
后缀表达式#xff1a;别称逆波兰式#xff0c;指的是严格从左向右按照运算符出现的顺序进行计算#xff0c;不包…一、基本概念
中缀表达式运算符都在运算数之间的表达式也就是我们日常见到的表达式包含括号。例如(12)*5
后缀表达式别称逆波兰式指的是严格从左向右按照运算符出现的顺序进行计算不包含括号运算符都放在运算对象的后面的。例如1 2 5 * 就是一个后缀表达式是由前面中缀表达式的例子转换的。
为什么要转换成后缀表达式中缀表达式不行吗
那是因为对于一个中缀表达式 58/2 我们人可以轻易知道各运算的次序得到答案 9 可是计算机不能计算机很笨所以需要转换成后缀表达式 5 8 2 / 这样计算机就能在不考虑各符号优先级的情况下也得出答案 9计算机从左向右遍历将5、8、2入栈遇到 / 将8、2出栈将 8/2 的结果入栈此时栈中有 5 4 遇到 将5、4出栈将 54 的结果入栈遍历完了栈中有 9这就是答案。 二、中缀表达式转后缀表达式----栈的应用 思路先从左向右遍历整个中缀表达式 1、如果是运算数直接输出到后缀表达式 2、遇到左括号 ( 压入栈中把左括号当做优先级最低的符号 3、遇到右括号 ) 意味着括号中的运算结束了将运算符一个一个弹出栈顶并且输出到后缀表达式直到遇到左括号但是左括号不加入到后缀表达式 4、对于运算符 - * / 1.如果优先级大于栈顶的运算符或者栈为空时入栈 2.否则即优先级小于等于栈顶的运算符就将栈顶依次弹出到后缀表达式中去直到满足入栈条件。 此时是优先级最低的符号 遍历完中缀表达式后可能栈中还存有运算符依次弹出直至栈空。
转换过程分析以(35)*3-2/1为样例结果是3 5 3 * 2 1 / - 1.遍历到(入栈 后缀表达式为 栈中元素( 2.遍历到3输出到后缀表达式 后缀表达式为3 栈中元素( 3.遍历到优先级1大于栈顶元素(的优先级入栈 后缀表达式为3 栈中元素( 4.遍历到5输出到后缀表达式 后缀表达式为3 5 栈中元素( 5.遍历到)一直出栈输出到后缀表达式直到遇到(但是(不加入后缀表达式 后缀表达式为3 5 栈中元素 6.遍历到*栈为空入栈 后缀表达式为3 5 栈中元素* 7.遍历到3输出到后缀表达式 后缀表达式为3 5 3 栈中元素* 8.遍历到-小于等于*的优先级*出栈输出到后缀表达式-入栈 后缀表达式为3 5 3 * 栈中元素- 9.遍历到2输出到后缀表达式 后缀表达式为3 5 3 * 2 栈中元素- 10.遍历到//的优先级大于-入栈 后缀表达式为3 5 3 * 2 栈中元素-/ 11.遍历到1输出到后缀表达式 后缀表达式为3 5 3 * 2 1 栈中元素-/ 12.遍历完了可是栈未空出栈直至栈空 后缀表达式为3 5 3 * 2 1 / - 栈中元素 至此结束 。
三、代码
转换代码
int priority(char ch) //返回优先级-优先级越高值越大
{if (ch (){return 0;}else if (ch || ch -){return 1;}else // * /{return 2;}
}void trans(string arr1, string arr2)
{Stack stack;initStack(stack);DateElem e ; //用于传出栈中元素for (int i 0; i arr1.size(); i) //每次arr2加入元素后都加一个空格以分割{if (arr1[i] ) //跳过空格{continue;}if(arr1[i] 0 arr1[i] 9) //情况1{while (arr1[i] 0 arr1[i] 9){arr2.push_back(arr1[i]);i;}arr2.push_back( );i--; //因为当不是数字时i也了i等下循环中还要所以得--}else if (arr1[i] ( ) //情况2{pushStack(stack, arr1[i]);}else if (arr1[i] )) //情况3{while (!IsEmpty(stack) getTop(stack)!(){popStack(stack, e);arr2.push_back(e);arr2.push_back( );}if(getTop(stack) ()popStack(stack,e); //将 ( 弹出栈}else //情况4{while (!IsEmpty(stack) priority(getTop(stack) ) priority( arr1[i] )) //栈不为空 并且 栈顶元素优先级大于等于遍历的字符{popStack(stack, e);arr2.push_back(e);arr2.push_back( );}pushStack(stack, arr1[i]); //循环结束就满足入栈条件栈为空 或者 优先级小于栈顶元素}}while (!IsEmpty(stack)) //输出栈中剩余的元素{popStack(stack, e);arr2.push_back(e);arr2.push_back( );}return;}
全部代码
#define _CRT_SECURE_NO_WARNINGS 1#include iostream
#include stringusing namespace std;//栈的数据结构定义
#define MAX_SIZE 120typedef char DateElem;
typedef struct _Stack
{DateElem* top;DateElem* base;
}Stack;//初始化栈
bool initStack(Stack s)
{s.base new DateElem[MAX_SIZE];if (!s.base) return false; //空间分配失败s.top s.base; //空栈return true;
}//入栈
bool pushStack(Stack s, DateElem e)
{if (!s.base || (s.top - s.base) MAX_SIZE) return false; //栈没建立 或者 栈满了*(s.top) e;return true;
}//出栈
bool popStack(Stack s, DateElem e)
{if (!s.base || s.base s.top) return false;e *(--s.top); //先将栈顶元素赋值给e栈顶指针再移动因为栈顶指针都是指向栈顶元素的后一个位置return true;
}//获取栈顶元素
DateElem getTop(Stack s)
{if (s.top s.base) //栈不为空{return *(s.top - 1);}else{cout 栈为空 endl;return 1;}
}//判断栈是否为空
bool IsEmpty(Stack s)
{if (s.base s.top){return true;}else{return false;}}//获取栈中元素的个数
int getLength(Stack s)
{return (int)(s.top - s.base);
}//销毁栈
void destoryStack(Stack s)
{//与初始化栈一一对应if (s.base ! NULL) //有效{delete s.base;s.base s.top NULL;}}int priority(char ch) //返回优先级-优先级越高值越大
{if (ch (){return 0;}else if (ch || ch -){return 1;}else // * /{return 2;}
}void trans(string arr1, string arr2)
{Stack stack;initStack(stack);DateElem e ; //用于传出栈中元素for (int i 0; i arr1.size(); i) //每次arr2加入元素后都加一个空格以分割{if (arr1[i] ) //跳过空格{continue;}if(arr1[i] 0 arr1[i] 9) //情况1{while (arr1[i] 0 arr1[i] 9){arr2.push_back(arr1[i]);i;}arr2.push_back( );i--; //因为当不是数字时i也了i等下循环中还要所以得--}else if (arr1[i] ( ) //情况2{pushStack(stack, arr1[i]);}else if (arr1[i] )) //情况3{while (!IsEmpty(stack) getTop(stack)!(){popStack(stack, e);arr2.push_back(e);arr2.push_back( );}if(getTop(stack) ()popStack(stack,e); //将 ( 弹出栈}else //情况4{while (!IsEmpty(stack) priority(getTop(stack) ) priority( arr1[i] )) //栈不为空 并且 栈顶元素优先级大于等于遍历的字符{popStack(stack, e);arr2.push_back(e);arr2.push_back( );}pushStack(stack, arr1[i]); //循环结束就满足入栈条件栈为空 或者 优先级小于栈顶元素}}while (!IsEmpty(stack)) //输出栈中剩余的元素{popStack(stack, e);arr2.push_back(e);arr2.push_back( );}return;}
int main(void)
{Stack stack;initStack(stack);string arr1 ;string arr2 ;cout 请输入中缀表达式; //((12)*3)-(6-5)getline(cin, arr1);trans(arr1, arr2);cout 转为后缀表达式为; //1 2 3 * 6 5 - -cout arr2 endl;return 0;
}
其中包括了栈的代码你也可以使用库中的栈。
