带括号的中缀表达式的运算(整数的加减乘除)
运算符优先分析法
Author: xzc
2019.11.29 编译原理实验课
输入：
begin x:= expression ;end$#
输出：
the result of the expression and
the possible Error Message(s)
功能：
判断算术表达式的合法性 (括号匹配，空括号等等)，并且
计算带括号'(',')'的整数加减乘除四则运算的算术表达式的值
Sample Input
begin a:=2+3* 4-10 /5;end$#
begin b:=2-3+4*6-10/5*2-1;end$#
begin c:=2+3 *((5-1)*8-6)/4-100/50;end$#
begin d:=3* -5+6;end$#
begin e:=( 3 *4-5)/6+((4/3);end$#;
begin f:=(11+34)/2+()/6;end$#;
My OutPut
The expression is：2+3* 4-10 /5
12 = 3 * 4
14 = 2 + 12
2 = 10 / 5
12 = 14 - 2
The answer of this express is: 12
The expression is：2-3+4*6-10/5*2-1
-1 = 2 - 3
24 = 4 * 6
23 = -1 + 24
2 = 10 / 5
4 = 2 * 2
19 = 23 - 4
18 = 19 - 1
The answer of this express is: 18
The expression is：2+3 *((5-1)*8-6)/4-100/50
4 = 5 - 1
32 = 4 * 8
26 = 32 - 6
78 = 3 * 26
19 = 78 / 4
21 = 2 + 19
2 = 100 / 50
19 = 21 - 2
The answer of this express is: 19
The expression is：3* -5+6
Input Error!
The expression is：( 3 *4-5)/6+((4/3)
The bracket of this expression is not match!
The expression is：(11+34)/2+()/6
There is a bracket which has nothing inside it
--------------------------------
Process exited after 5.433 seconds with return value 0
请按任意键继续. . .
用到的知识or技巧
1. 括号匹配的检测
利用栈，是左括号就入栈，是右括号就弹栈(栈空了就说明缺少左括号)
非括号字符直接忽略
最后如果栈空就匹配，栈不空说明缺少右括号
代码如下：
bool isBracketMatch(int st,int ed,char * s)
//判断s[st]到s[ed-1]括号是否匹配，是则返回true
{
stack<char> Stack;
for(int i=st;i<ed;++i)
{
switch (s[i]){
case '(':
Stack.push(s[i]);
break;
case ')':
if(Stack.empty()) return false;
Stack.pop();
break;
}
}
return (Stack.empty());
}
2. 中缀表达式的计算：
- 我们知道后缀表达式是可以直接运算的，中缀表达式还要考虑运算符的优先级，我们知道括号优先级最高，乘除次之，加减最低，所以可以先定义一个函数返回运算符的优先级
//返回数字具体是多少无所谓，只要能反应运算符(终结符)之间优先级大小关系即可
int favor(char ch)
{
switch (ch){
case '#':
return 0;
case '+':
case '-':
return 5;
case '*':
case '/':
return 6;
case '(':
return 1;
case ')':
return 66;
default:
return 100;
}
return 100;
}
- 在解析表达式的时候，我们需要读取一个整数，这个整数可能不止一位，我们用x = x*10+s[i]-'0’的方法获取整数
int getOperand(int& i)
{
int k=i,x=0;
for(;s[k]!=';'&&isdigit(s[k]);++k)
x = x*10+s[k]-'0';
i = k-1;
return x;
}
- 我们相当于先转化为后缀表达式再计算。后缀表达式是用栈一遍pop一边计算，从后往前。那么在栈顶的先算，在栈底的后算。所以栈中运算符的优先级肯定是要从小到大单调递增才对(因为同一优先级一般是左结合，所以栈中运算符优先级相等也会出问题)。
- 我们创建一个操作数栈Num,一个运算符栈op, 然后遇到操作数就直接入操作数栈Num.push()。遇到运算符，我们就判断运算符栈栈顶的元素优先级是不是比当前运算符小，小的话直接入栈，favor(top()) >= favor(s[i])的话，就运算符栈出栈，操作数栈出栈两次，分别得到右操作数rhs和做操作数lhs, 用top()表示的运算完成二元运算后，把计算结果再入栈，Num.push(ans)
//计算二元运算的结果
int cal(int lhs,char op,int rhs)
{
switch (op){
case '+':return lhs+rhs;
case '-':return lhs-rhs;
case '*':return lhs*rhs;
case '/':
if(!rhs)
{
cout<<"Logical Error! Divided by zero!
";
exit(-1);
}
return lhs/rhs;
}
return 0;
}
- 我们可以把pop操作符一次，pop操作数两次，运算，push操作数的这个过程封装成一个函数：
//如果出现不合法情况就返回false
bool Pop_Cal(stack<int>& Num,stack<char>& op)
{
if(Num.empty())
{
cout<<"Input Error!
";
return false;
}
int rhs = Num.top(); Num.pop();
if(Num.empty())
{
cout<<"Input Error!
";
return false;
}
int lhs = Num.top(); Num.pop();
char oper = op.top(); op.pop();
bool yes = true;
int ans = cal(lhs,oper,rhs,yes);
if(!yes) return false;
Num.push(ans);
printf("%d = %d %c %d
",ans,lhs,oper,rhs);
return true;
}
- 还有，整行读入要用cin.getline(str,maxLen) 或者getline(cin,str);
- 对于括号来说，它可以改变其它运算的优先顺序。所以对于括号我们这样处理：
如果是左括号，直接入栈
如果是右括号，计算栈中的值，popAndCal直到遇到第一个左括号才能结束
这个也好理解，因为带了括号的要先算，在栈顶的也先算，如果后面的优先级比我当前栈顶的优先级还要低，那我只能先计算出来 - 最后运算符栈可能会剩下从栈底到栈顶优先级递增的一系列运算符，那么操作数栈肯定也会有相应个数+1的操作数剩余，只要计算后缀表达式，pop,cal,puah即可
while(op.top()!='#')
{
OK = Pop_Cal(Num,op);
if(!OK) return; //OK=false表示输入不合法
}
- 因为pop运算符栈的时候要经常判栈是否空，所以我们可以在所有计算之前先往操作符栈op中压栈push进去优先级最低的‘#’(自己定义，合理即可)
完整代码
#include<bits/stdc++.h>
//#define FileInput 1
using namespace std;
char s[100005];
int favor(char ch); //返回运算符的优先级
int cal(int lhs,char op,int rhs);//计算lhs op rhs二元表达式的结果
bool Pop_Cal(stack<int>& Num,stack<char>& op);//操作数运算符出栈并运算
void getOperand(int & i,stack<int>& Num);//获取操作数
bool isBracketMatch(int st,int ed);//判断表达式括号是否匹配
bool emptyBetweenBracket(int st,int ed); //两个括号之间啥都没有
void solve(int st,int ed); //求表达式的值
int main()
{
#ifdef FileInput
freopen("in.txt","r",stdin);
#endif
while(cin.getline(s,100000))
{
int st=0;
while(!isdigit(s[st])&&s[st]!='(')
st++;
int ed = 0;
printf("The expression is：");
for(ed=st;s[ed]!=';';++ed)
printf("%c",s[ed]);printf("
");
if(!isBracketMatch(st,ed))
{
printf("The bracket of this expression is not match!
");
continue;
}
if(emptyBetweenBracket(st,ed))
{
printf("There is a bracket which has nothing inside it
");
continue;
}
solve(st,ed);
printf("
");
}
#ifdef FileInput
fclose(stdin);
#endif
return 0;
}
int favor(char ch)
{
switch (ch){
case '#':
return 0;
case '+':
case '-':
return 5;
case '*':
case '/':
return 6;
case '(':
return 1;
case ')':
return 66;
default:
cout<<"Error! Illegal Operator"<<ch<<"!
";
return 100;
}
cout<<"Error!
";
return 100;
}
int cal(int lhs,char op,int rhs,bool& ok)
{
ok = true;
switch (op){
case '+':return lhs+rhs;
case '-':return lhs-rhs;
case '*':return lhs*rhs;
case '/':
if(!rhs)
{
cout<<"Logical Error! Divided by zero!
";
ok = false;
return -1000000000;
}
return lhs/rhs;
}
return 0;
}
bool Pop_Cal(stack<int>& Num,stack<char>& op)
{
if(Num.empty())
{
cout<<"Input Error!
";
return false;
}
int rhs = Num.top(); Num.pop();
if(Num.empty())
{
cout<<"Input Error!
";
return false;
}
int lhs = Num.top(); Num.pop();
char oper = op.top(); op.pop();
bool yes = true;
int ans = cal(lhs,oper,rhs,yes);
if(!yes) return false;
Num.push(ans);
printf("%d = %d %c %d
",ans,lhs,oper,rhs);
return true;
}
void getOperand(int & i,stack<int>& Num)
{
int x=0;
int k=i;
for(;s[k]!=';'&&isdigit(s[k]);++k)
{
x = x*10+s[k]-'0';
}
i=k-1;
Num.push(x);
}
bool isBracketMatch(int st,int ed)
{
stack<char> Stack;
for(int i=st;i<ed;++i)
{
switch (s[i]){
case '(':
Stack.push(s[i]);
break;
case ')':
if(Stack.empty()) return false;
Stack.pop();
break;
}
}
return (Stack.empty());
}
bool emptyBetweenBracket(int st,int ed) //两个括号之间啥都没有
{
for(int i=st;i<ed-1;++i)
if(s[i]=='('&&s[i+1]==')') return true;
return false;
}
void solve(int st,int ed)
{
stack<int> Num;
stack<char> op;
bool ok = true;
op.push('#');
if(s[st]=='-'||s[st]=='+')
Num.push(0);
for(int i=st;i<ed;++i)
{
if(s[i]==' ') continue;
if(isdigit(s[i])) //是操作数
{
getOperand(i,Num);
}
else
{
char ch = s[i];
switch (ch)
{
case '(':
op.push('(');
break;
case ')':
while(op.top()!='(')
{
ok = Pop_Cal(Num,op);
if(!ok) return;
}
op.pop();
break;
case '+':case '-':case '*':case '/':
while(favor(op.top())>=favor(ch))
{
ok = Pop_Cal(Num,op);
if(!ok) return;
}
op.push(ch);
break;
default:
cout<<"Input Error!"<<ch<<"is illegal!
";
return;
}
}
}
while(op.top()!='#')
{
ok = Pop_Cal(Num,op);
if(!ok) return;
}
printf("The answer of this express is: %d
",Num.top());
}
喜欢就点个赞吧^_^