表达式求值
给定一个表达式
例 ：1+2*3=
输出： 7
对于每个运算符号 ，前面的符号与现在入栈的符号比较
打表 表示其优先级
使用两个栈 opd和opr
一个存入数字 一个存入运算符号
用topd和topr记录栈头
noip2005等价表达式 用到此知识
http://blog.csdn.net/xljer_/article/details/71663202
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
//大于 -->计算 小于-->入栈
char r[9][9] = {
{' ','+','-','*','/','(',')','^','='},
{'+','>','>','<','<','<','>','<','>'},
{'-','>','>','<','<','<','>','<','>'},
{'*','>','>','>','>','<','>','<','>'},
{'/','>','>','>','>','<','>','<','>'},
{'(','<','<','<','<','<','=','<',' '},
{')','>','>','>','>',' ','>','>','>'},
{'^','>','>','>','>','<','>','>','>'},
{'=','<','<','<','<','<',' ','<','='},
};
char ss(char x,char y){//判断优先级函数
int a,b;
switch(x){//分情况
case '+':
a=1;
break;
case '-':
a=2;
break;
case '*':
a=3;
break;
case '/':
a=4;
break;
case '(':
a=5;
break;
case ')':
a=6;
break;
case '^':
a=7;
break;
case '=':
a=8;
break;
}
switch(y){//同上
case '+':
b=1;
break;
case '-':
b=2;
break;
case '*':
b=3;
break;
case '/':
b=4;
break;
case '(':
b=5;
break;
case ')':
b=6;
break;
case '^':
b=7;
break;
case '=':
b=8;
break;
}
return r[a][b];
}
int ct(int x,int y,char ch){//计算结果函数
switch(ch){
case '+':
return x+y;
break;
case '-':
return x-y;
break;
case '*':
return x*y;
break;
case '/':
return x/y;
break;
case '^':
return pow(x,y);
break;
}
}
int opd[100],topd,topr=1,a,b,c;
char opr[100],ch,cch;
int main(){
opr[1]='=';//提前在栈顶存入一个 等于 如果栈中只剩两个等于代表运算结束
ch=getchar();
while(!(ch=='='&&opr[topr]=='=')){
if(ch>='0'&&ch<='9') {
opd[++topd]=ch-48;
ch=getchar();
}
switch(ss(opr[topr],ch)){
case '<'://前一个运算符小于现在读入的运算符 入栈
opr[++topr]=ch;
ch=getchar();
break;
case '>'://前一个运算符大于现在读入的运算符 计算结果
a=opd[topd--];
b=opd[topd--];
cch=opr[topr--];
c=ct(b,a,cch);
opd[++topd]=c;
break;
case '='://遇到括号 删去括号
topr--;
ch=getchar();
break;
}
}
cout<<opd[1];//最后opd[1]中是答案
return 0;
}系统栈写法 代码如下
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<stack>
using namespace std;
//大于 -->计算 小于-->入栈
char r[9][9] = {
{' ','+','-','*','/','(',')','^','='},
{'+','>','>','<','<','<','>','<','>'},
{'-','>','>','<','<','<','>','<','>'},
{'*','>','>','>','>','<','>','<','>'},
{'/','>','>','>','>','<','>','<','>'},
{'(','<','<','<','<','<','=','<',' '},
{')','>','>','>','>',' ','>','>','>'},
{'^','>','>','>','>','<','>','>','>'},
{'=','<','<','<','<','<',' ','<','='},
};
char ss(char x,char y){//判断优先级函数
int a,b;
switch(x){//分情况
case '+':
a=1;
break;
case '-':
a=2;
break;
case '*':
a=3;
break;
case '/':
a=4;
break;
case '(':
a=5;
break;
case ')':
a=6;
break;
case '^':
a=7;
break;
case '=':
a=8;
break;
}
switch(y){//同上
case '+':
b=1;
break;
case '-':
b=2;
break;
case '*':
b=3;
break;
case '/':
b=4;
break;
case '(':
b=5;
break;
case ')':
b=6;
break;
case '^':
b=7;
break;
case '=':
b=8;
break;
}
return r[a][b];
}
int ct(int x,int y,char ch){//计算结果函数
switch(ch){
case '+':
return x+y;
break;
case '-':
return x-y;
break;
case '*':
return x*y;
break;
case '/':
return x/y;
break;
case '^':
return pow(x,y);
break;
}
}
stack<int>opd;
stack<char>opr;
int a,b,c;
char ch,cch;
int main(){
opr.push('=');
ch=getchar();
int flag=0;
while(!(ch=='='&&opr.top()=='=')){
if(ch>='0'&&ch<='9') {
opd.push(ch-48);
flag=1;
ch=getchar();
}
while(ch>='0'&&ch<='9'&&flag==1) {
int x=opd.top();
opd.pop();
x=x*10+ch-48;
opd.push(x);
ch=getchar();
}
flag=0;
switch(ss(opr.top(),ch)){
case '<'://前一个运算符小于现在读入的运算符 入栈
opr.push(ch);
ch=getchar();
break;
case '>'://前一个运算符大于现在读入的运算符 计算结果
a=opd.top();
opd.pop();
b=opd.top();
opd.pop();
cch=opr.top();
opr.pop();
c=ct(b,a,cch);
opd.push(c);
break;
case '='://遇到括号 删去括号
opr.pop();
ch=getchar();
break;
}
}
cout<<opd.top();//最后opd.top()中是答案
return 0;
}