MyException - 我的异常网
当前位置:我的异常网» C++ » 栈的应用求解表达式的一个有关问题,多谢

栈的应用求解表达式的一个有关问题,多谢

www.MyException.Cn  网友分享于:2015-02-11  浏览:0次
栈的应用求解表达式的一个问题,谢谢!
首先说明一下用栈的原理把中缀表达式转成后缀表达式的大致步骤:
1.遇到操作数:直接输出(添加到后缀表达式中)
2.栈为空时,遇到运算符,直接入栈
3.遇到左括号:将其入栈
4.遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出。
5.遇到其他运算符:加减乘除:弹出优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈
6.最终将栈中的元素依次出栈,输出。
我的代码功能是把中缀表达式转成后缀表达式:
但是有一个问题,好像是J的问题,J不知道为什么突变到了100多,导致输出结果错误
#include<iostream>
#include<cctype>
#include<cstring>
using namespace std;
typedef char datatype;
const int maxlen=100;
struct stack
{   int top;
   datatype array[maxlen];
};
void initstack(stack& s)//初始化栈 
{ s.top=-1;}
void push(stack& s,datatype x) //进栈操作 
{s.array[++s.top]=x;}
 datatype peek(stack& s)//查看栈顶元素值 
 {return s.array[s.top];}
datatype pop(stack& s) //删除栈顶元素并返回其值 
{return s.array[s.top--];}
bool empty(stack& s)//判断栈是否为空 
{return s.top==-1;}
bool isoperator(char ch)
{return ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%'||ch=='^';}
bool priority(char ch1,char ch2)//优先级比较
{ int mark1,mark2;
switch (ch1)
{case '+':
 case '-':mark1=1;break;
 case '*':
 case '/':
 case '%':mark1=2;break;
 case '^':mark1=3;break;}
 switch (ch2)
{case '+':
 case '-':mark2=1;break;
 case '*':
 case '/':
 case '%':mark2=2;break;
 case '^':mark2=3;break;}
 return mark1>mark2;
}
void trans(char* infix,char* postfix)//将中缀表达式转为后缀表达式 
{
  stack s;
  initstack(s); 
  char ch;
  int j=0;
 int i=0;
  while(i<strlen(infix))
  { ch=infix[i];
   if(ch=='(') {    //左括号直接入栈
   push(s,ch);i++;}
   else if(ch==')')    //右括号则把栈内元素弹出直到遇见左括号
   {while(peek(s)!='(')
   postfix[j++]=pop(s);
   pop(s);
   i++;}//弹出右括号
   else if(isoperator(ch))
   {if(empty(s))//如果栈为空,第一个操作符直接进入栈内 
   {push(s,ch);i++;}
   else if(priority(ch,s.array[s.top]))  //如果栈不为空,则比较该操作符与栈顶元素的优先级,若栈顶元素优先级低于该操作符,则操作符直接入栈 
    {push(s,ch);i++;}
else      //若栈顶元素优先级高于或等于读入操作符优先级则依次弹出栈顶元素直到栈顶元素优先级低于读入操作符时停止弹出
 {
 while(!priority(ch,s.array[s.top])&&!empty(s)) 
 postfix[j++]=pop(s);
 push(s,ch);//操作符进栈 
 i++;}
 } 
   else
  {
  while(!isoperator(ch)) //一位位的读取字符,为数字或者小数点时(即不是操作符时)写入后缀表达式中 
   {postfix[j++]=ch;ch=infix[++i];}
   postfix[j++]=' ';}//在数字的末尾加一个空格防止在处理后缀表达式时出现误读的情况,如12,不知道是数字12还是1和2两个数字

cout<<"栈:";
for(int k=0;k<=s.top;k++)
cout<<s.array[k]<<endl; 
cout<<"j:"<<j<<endl; 
 }
 while(!empty(s))   //此时读取中缀表达式完毕,将栈中剩余的操作符输入到后缀表达式中
     postfix[j++]=pop(s);
 postfix[j]=0; 
   }
int main(){
char infix[100];
char postfix[100];
cout<<"请输入你想要求解的表达式:"<<endl; 
gets(infix);
trans(infix,postfix);
cout<<postfix;
return 0;
}


不知道为什么会这样。。。
------解决思路----------------------
问题出在这一句:

while(!isoperator(ch))
{
        postfix[j++]=ch;
        ch=infix[++i];
 }


如果ch是表达式的最后一个数字,它后面就没有运算符了,这个循环就会一直进行下去,由于infix数组未初始化,后面都是一些垃圾值,运气好撞到一个运算符就停下来,运气不好直接stack overflow
------解决思路----------------------
您的107,运算过程是这样的:(2+3)*(3+4)*3+2  ................
如果您输入的表达式是7+4-3*1,估计程序输出的结果是88。。。

文章评论

鲜为人知的编程真相
鲜为人知的编程真相
 程序员的样子
程序员的样子
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
每天工作4小时的程序员
每天工作4小时的程序员
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
我是如何打败拖延症的
我是如何打败拖延症的
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
代码女神横空出世
代码女神横空出世
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
程序员和编码员之间的区别
程序员和编码员之间的区别
漫画:程序员的工作
漫画:程序员的工作
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
老程序员的下场
老程序员的下场
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
我的丈夫是个程序员
我的丈夫是个程序员
Java程序员必看电影
Java程序员必看电影
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
一个程序员的时间管理
一个程序员的时间管理
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员的鄙视链
程序员的鄙视链
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
10个调试和排错的小建议
10个调试和排错的小建议
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
编程语言是女人
编程语言是女人
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
旅行,写作,编程
旅行,写作,编程
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
程序员必看的十大电影
程序员必看的十大电影
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员都该阅读的书
程序员都该阅读的书
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有